Minimum spanning tree
Minimum spanning tree (MST) - undirected graph'dagi barça özaro boğlangan vertex'larni öz içiga olgan (spanning) va aylana bölmagan (acyclic) sub-graph'lar içidan minimum weight'li sub-graph.
#undirected graph
Kenigsbergning yetti köprigi
Kenigsberg (Königsberg, hozirgi Kaliningrad) şahridagi yetti köprikni qanday qilib bir köprikga ikki marta çiqmasdan bosib ötiş - qadimiy matematik masalalardan biri bölib, birinçi marta 1736-yilda Leonard Eyler tomonidan yeçilgan. Eyler har bir köprikdan faqat bir marta foydalanib barça köpriklarni
Graph'dagi aylanalarni topiş
Graph'da aylana (cycle) nimaligi haqida graph atamalarida tuşuntirilgan. Bir graph'da aylanalar bir neça bölişi mumkin.
Graph masalalari. Bipartite graph
Agar graph'ning har bir vertex'i qarama-qarşi tomondagi vertex'ga boğlanuvçi ikki subset'ga (qismga) ajraladigan bölsa, demak graph - bipartite böladi.
Graph'da boğlangan komponentlar
Boğlangan komponentlar (Connected components, CC) deb graphdagi bir-biriga toğridan töğri yoki oradagi vertex'lar orqali boğlangan komponentlar töplamiga aytiladi. Amaliyotda agar ikki vertex orasida path bölsa, biz ularni boğlangan deb ayta olamiz.
Graph'ni kodda ifodalaş. Graph API
Graph ma'lumotlar tuzilmasini kodda ifodalaşning bir neça usullari bor. Amaliyotda qöyiladigan masalaga qarab usullardan biri tanlanadi.
Graph ma'lumotlar tuzilmasi
Biz çiziqli bölmagan ma’lumotlar tuzilmasini örganişni boşlaganimizda, ularning bazaviy xarakteristikasini körib çiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (heç bölmaganda sanoq tartibiga ega emas).