Kahealuseline graaf

Allikas: Vikipeedia
Jump to navigation Jump to search
Kahealuseline graaf

Kahealuseline graaf (inglise keeles bipartite) on graaf, mille tipud jagunevad kahte hulka, kus servad esinevad ainult erinevatesse hulkadesse kuuluvate tippude vahel.

Kahealuselise graafi täiendis moodustavad need alused klikke.

Kahealuselised on näiteks Folkmani graaf ja Heawoodi graaf.

Kui kõik hulkadevahelised tipud on servadega ühendatud, siis kujutab see graaf endast bi-klikki.

Graaf võib olla ka kolme-, nelja- või n-aluseline. Alused võivad olla kas võrdse või erineva suurusega.