Ойлер нарича цикъл графика, съдържащ всички ръбове на графиката.
Ойлер графика е свързан графика, в която е налице цикъл Ойлер. Ойлер графика може да се направи без повдигане молива от хартията и без повтаряне на линии (фиг. 14).
Фиг. 14. Ойлер графика
Теорема 6. графика G е Ойлеров ако и само ако G - свързан графика с всички четни върха.
Hamiltonian верига е проста верига, съдържащ всички върхове на графиката.
А Hamiltonian цикъл е Hamiltonian верига, в началото и в края на които са идентични.
Nazyvaetsyagamiltonovym графика ако има Hamiltonian цикъл (Фигура 15).
Фиг. 15. Hamiltonian графика
Графика G се нарича р - хроматичната, където р - цяло число, ако върховете могат да бъдат оцветени р - различни цветове, така че няма две съседни върха са оцветени същото.
Най-малкият брой стр за които графиката е р - хроматичната се нарича хроматичната броя на графика и определен. Ако = 2, тогава графиката се нарича bichromatic. А необходимо и достатъчно условие в колоната на странни цикли дължина.
Например, графиката на фиг. 16 bichromatic, неговите топ "цветни" две "цветове", етикетирани 0 и 1.
Фиг. 16. Двукомпонентна хроматичната графика.
Плоски и равнинни графики
Графика G е равнинна (плосък), ако има изоморфен го Ърл G ", в която образът на самолетни ръбове се пресичат само във върховете. С други думи, няма две равнинни графиката ръбове са разединени, с изключение на общи върхове. Например, графиката на фиг. 5 е плоска, както е показано на фиг. 7 - не.
Теорема на Ойлер. Свързана планарна графика с п върхове и ръбове т к разделя равнината на региони (включително външно) и
Графиката е двустранен ако комплектът на върховете X може да бъде разделен на две несвързани подгрупи, така че всяка графика ръб свързва два върха от различни подгрупи.
Свързани статии