Граф

[shadowhr]

1 Намерете върховото и ребровото хроматично число на графа
2 Съществува ли в дадения граф
а) хамилтонов цикъл;
б) хамилтонов път;
в) затворена ойлерова верига;
г) отворена ойлерова верига?
3 Докажете, че даденият граф е планарен.
Най -малко колко ребра трябва да се добавят, та графът да стане непланарен?

[Knowledge Greedy]

3. Преместването на върха [tex]A[/tex] във вътрешността на областта [tex]BCD[/tex] доказва, че графът е планарен - няма пресичащи се ребра.

Планарен граф.png (32.31 KiB) Прегледано 570 пъти

Добавянето на [tex]1[/tex] ребро не е достатъчно да направи графа непланарен. Например с добавянето на [tex]GD[/tex] графът остава планарен (както стана с реброто [tex]DA[/tex], само че тук вкарваме върха [tex]G[/tex] в областта [tex]DEF[/tex]).
Но добавянето на две ребра - свързващи връх на графа с два върха, които са от различни области с общ контур, прави графа непланарен. Пресичането на някои две ребра няма как да бъде избегнато в равнината - например с добавянето на [tex]GD[/tex] и [tex]GB[/tex] .