Tashkent informaciya texnologiyalari universiteti

19 Tema: Planar graflar. Tegis graflar haqqında Eyler formulasi. Gomeomorfizm, Kuratovskiy teoremasi.
Reje :
1. Planar graflari.
2. Pontryagin-Kuratovskiy teoremasi.
3. Planar grafning xromatik sanın
bahalaw.
Grafik teoriyasında planar grafik tegislikke yotqizilishi múmkin bolǵan grafik bolıp tabıladı, yaǵnıy onı tegislikke sonday sızıw múmkin, onıń qırları tek aqırǵı noqatlarında kesiwedi. Basqasha etip aytqanda, shetleri bir-biri menen kesilispeytuǵın etip sızılıwı múmkin.[1][2] Bunday sızılma tegislik grafigi yamasa grafikdıń planar jaylasıwı dep ataladı. Tegis grafiktı tegisliktegi hár bir túyinnen noqatqasha hám sol tegisliktegi hár bir shetten tegislik iymek sızig'igacha bolǵan kartalawdan ibarat bolǵan planar grafik retinde tariyplanishi múmkin, sonda hár bir iymek sızıqtıń oǵada noqatları onıń aqırınan kartalanǵan noqatlar bolıp tabıladı. túyinler hám barlıq iymek sızıqlar bir-birinen ajralıp turadı, olardıń ekstremal noqatlarınan tısqarı.
Tegislikte sızıw múmkin bolǵan hár bir grafik sferada da sızılıwı múmkin hám kerisinshe, stereografik proyeksiya járdeminde.
Samolyot grafikları kombinatsion kartalar yamasa aylanıw sistemaları menen kodlanıwı múmkin.
Sferadagi tapologik ekvivalent sızılmalardıń ekvivalentlik klassi, ádetde, istmuslarning joq ekenligi sıyaqlı qosımsha shamalarǵa iye, planar karta dep ataladı. Tegis grafik sırtqı yamasa shegaralanbaǵan betke iye bolsa -de, planar kartanıń júzleriniń hesh biri bólek mártebege iye emes.
Planar grafiklar málim bir jinsning maydanında sızılǵan grafiklarǵa ulıwmalastırıladı. Bul terminologiyada planar grafiklar 0 jinsga iye, sebebi tegislik (hám shar) 0 jinsining sirtlari bolıp tabıladı.


20 Tema: Baģdarlanģan graf. Baģdarlanģan graf ushın qońsiliq matritsalari. Baģdarlanģan graflarda marshrut, shınjır, cikl


Reje:

1. 
   Baģdarlanģan graflarda marshrut, shınjır, cikl.
   

Qırdıń bası yamasa aqırın ańlatiwshı uchga bul qırǵa intsident úsh dep ataladı. Graf uchining dárejesi dep bul uchga intsident qırlar sanına aytıladı.

XI uchning dárejesin P (xi) menen belgilenedi.

Basqasha aytqanda úshten shıǵıwshı qırlar sanı uchning dárejesi esaplanadı. Dárejesi 1 ge teń úsh osilgan úsh boladı. Hesh qanday ayqulaq yamasa qırlarǵa iye bolmaǵan hám izolyatsiyalangan úshlerden ibarat graf nol graf dep ataladı. Kórinip turıptı, olda, nol grafning úshleri dárejesi nolǵa teń.

Lemma. Eger grafning barlıq úshleriniń dárejeleri 2 den úlken yamasa 2 ge teń bolsa, graf, álbette, konturdı óz ishine aladı. Eger grafning úshleri hám qırları kompleksinde refleksivlik hám simmetriklik ózgesheliklerin qánaatlantıratuǵın binar munasábet ámeldegi bolsa, bunday graf tolerant graf dep ataladı. Teorema. Oriyentirlanmagan graf eyler sikli bolıwı ushın onıń úshleri jup dárejelerge ıyelewi jáne onıń baylanıslı graf bolıwı zárúr hám jetkilikli bolıp tabıladı.

Pontryagin-Kuratovskiy). G graf planar boladı, tek hám tek sol haldaki, G graf K5 yamasa K3;3 ke gomemorof bolǵan, bólim graflarga iye bolmasa.