3.01.2. Основні типи графів

Граф називаєтьсяПустим, якщоE(G) = Æ, тобто, якщо в ньому немає ребер. Порожній граф порядкуNпозначається0N. Граф01 називаєтьсяТривіальним.Граф, в якому будь-які дві вершини з'єднані ребром називаєтьсяПовним.Повний граф порядкуNпозначаєтьсяKn.

Неважко підрахувати, що графKnмаєN(N-1)/2 ребер.

Граф такого виду як на рис. 1, називаєтьсяПростим ланцюгом.Простий ланцюг порядкуNпозначаєтьсяPn(на малюнку 1 зображено ланцюг>P4). Проста ланцюгPnмаєN-1 ребер.

Замкнуті ланцюги, тобто такі графи, як на рис. 2, називаютьсяПростими циклами.Простий цикл порядкуNпозначаєтьсяCn(на рис. 2 зображено простий ланцюгС7). Зрозуміло, що простий ланцюгCnмає стільки ж ребер, скільки і вершин, тобтоN.

Графи, такі як на рис. 3, називаються колесами.Колесо порядкуN+1 позначаєтьсяWn(на рис. 3 зображено колесоW7); воно має2Nребер.

Граф називаєтьсяДводольним, якщо безліч його вершин можна розбити на два непусті підмножини (частки) так, що жодні дві вершини однієї частки не є суміжними. (Аналогічно визначаються тридольні, чотиридольні і т. д. графи.) Таким чином, у дводольному графі суміжними можуть бути тільки вершини з різних часток (не обов'язково кожна з кожної). Приклад дводольного графа див. рис. 4.

Якщо ж у дводольному графі будь-які дві вершини з різних часток з'єднані рубом, то такий граф називаєтьсяПовним дводольним. Повний дводольний граф зNвершинами в одній частці та зMвершинами- в іншій позначаєтьсяKn, M. приклади:

ГрафиK1,NназиваєтьсяЗоряними графами, абоЗірками.

Зрозуміло, що існують графи, які можна віднести до кількох типів. Наприклад,K3=C3,K2=P2,K2, 2 =C4,K4=W3.

---