Eulerian és Hamilton-grafikonok
Az Eulerian egy gráf ciklusa, amely a gráf összes széleit tartalmazza.
Egy Euler gráf egy összefüggő gráf, amelyben van egy Euler ciklus. Az Euler-grafikát úgy lehet levonni, hogy a ceruzát a papíron levetik, és megismétli a vonalakat (14. ábra).
Ábra. 14. Euler gráf
Tétel 6. Egy G gráf Euler, ha és csak akkor, ha G egy összefüggő grafikon, amelynek minden csúcsa van.
A Hamilton-lánc egy egyszerű lánc, amely a gráf összes csúcsait tartalmazza.
A Hamilton-ciklus Hamilton-lánc, amelynek kezdete és vége egybeesik.
A gráfot Hamiltonnak nevezik, ha tartalmaz egy Hamilton-ciklust (15.
Ábra. 15. A Hamilton-gráf
A G gráfot p-kromatikusnak nevezik, ahol p természetes szám, ha a csúcsait p-különböző színekkel lehet színezni, így két szomszédos csúcstelennel nem azonos színű.
A legkisebb p számot, amelyre a grafikon p-kromatikus, a gráf kromatikus számát nevezzük és jelöljük. Ha = 2, akkor a gráfot bikromatikusnak nevezik. A páratlan hosszúságú ciklusok grafikonjában szükséges és elégséges feltétel.
Például a 3. ábrán látható grafikon. A 16 bikromatikus, a csúcsait "színesnek", két "színnel" jelölik, amelyeket 0 és 1 jelöli.
Ábra. 16. A bikromatikus gráf.
Lapos és sík grafikonok
A G gráf sík (sík), ha létezik egy G 'izomorf grafikon, amelynek képén a síkban a szélek csak a csúcsokon metszenek. Más szavakkal, egy sík grafikon esetében a két élnek nincs közös pontja, kivéve a közös csúcsokat. Például a 3. ábrán látható grafikon. Az 5. ábra sík, és a 3. ábrán. 7 nem.
Euler tétele. Egy kapcsolódó sík gráf n csúcsokkal és szélekkel osztja a síkot k tartományokba (beleértve a külsőt is), és
A grafikon kétpárti, ha az X csúcsainak halmaza két diszjunkt szubpontra osztható, oly módon, hogy a grafikon minden széle két különböző alcsoport csúcsához csatlakozik.