2. Элементы теории множеств

Grafiklar nazariyasining asosiy tushunchalari

Grafiklar nazariyasining asoschisi Leonhard Eyler Königsberg ko'priklari muammosida quruqlikning barcha to'rt qismidan o'tishning mumkin emasligini isbotlagan deb hisoblanadi (1736).

• Grafiklar nazariyasining asoschisi Leonhard Eyler Königsberg ko'priklari muammosida quruqlikning barcha to'rt qismidan o'tishning mumkin emasligini isbotlagan deb hisoblanadi (1736).

Grafiklar nazariyasi tarixidan

Asosiy tushunchalar

Grafik G=(V,E) ikki to'plamdan iborat: uchlari deb ataladigan chekli elementlar to'plami va qirralar deb ataladigan chekli elementlar to'plami .

Hisoblash _ G=(V, E)
V={v 1 , v 2 , v 3 , v 4 , v 5 } ;
E={e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 }

Asosiy tushunchalar

Vertices v i Va v j qirrasini belgilovchi e k chekkaning oxirgi uchlari e k deyiladi .

Oxirgi uchlari bir xil bo'lgan qirralar parallel deyiladi ( e 1 , e 4 ).

Pastadir yopiq chekka ( e 5 ) .

Cho'qqiga tegishli chekka deyiladi tasodifiy ( e 1 chekkasi v 1 uchlariga tushadi Va v 2 ) .

Asosiy tushunchalar

Izolyatsiya qilingan tepa emas cheksiz hodisadir ( v 3 ).

Ikki cho'qqi qo'shni bo'ladi , agar ular biron bir chekkaning oxirgi uchlari bo'lsa ( v 1 , v 4 ) .

Agar ikkita qirrada umumiy terminal uchi bo'lsa, ular qo'shni deyiladi . ( e 1 , e 2 ).

G

Asosiy tushunchalar

Subgraf - bu grafikning o'zi grafik bo'lgan har qanday qismi .

P od soni H ustun G