Определение. Дърво – това е краен свързан граф без цикли
Упражнение 1. Дайте пример за три различни дървета с 5 върха.
Упражнение 2. Докажете, че в дърво с nвърха има точно n–1 ребра.
Определение. Два графа се наричат изоморфни, ако можем така да преномерираме върховете на единия граф, че ако в единия граф i-ят връх е свързан с с ребро с j-я, то в другия също е така.
Кои от следните графи са изоморфни:
A: Върховете и ребрата на октаедра.
B: Върховете са клетките на дъска 23, ребрата – движението на топ.
C: Върховете са стените на куб, те са свързани с ребра, ако имат обща страна.
D: Върховете и страните на шестоъгълник.
E: Върховете са числата от 1 до 6, които са свързани с ребра, ако са взаимно прости.
F: Върховете са трибуквени думи, състоящи се от буквите И,К,С, а с ребра са свързани тези думи от тях, които са получени при замяната на две съседни букви.
Теорема 4. В свързан граф може да премахнем няколко ребра така, че да се получи дърво.
Определение. Дървото от предходната теорема се нарича основно дърво или скелетна графа.
5. Колко неизоморфни едно на друго дървета с 6 върха има?
6. а) Докажете, что от всяко крайно дърво може да премахнем един връх и всички излизащи от него ребра, така че графът да остане свързан.
б) Докажете същото за всеки краен граф.
7. За какъв най-малък брой ходове белите и черните коне на рисунката ще си сменят местата?
8. Летящ топ се движи както обикновено, но не може да стъпи на съседно поле. Колко различни затворени обходи на дъска 4х4 има за този топ?
Още задачи
ЕГ1. Докажете, че ако в дървото има ребро, то в него има не по-малко от 2 върха, от които излиза точно по едно ребро.
ЕГ2. Може ли в компания всеки да има точно по 6 познати, а всеки двама да имат точно по 2 познати?
Бургас, 9-10 класс, 23 июля 2016 г, www.ashap.info/Uroki/Bolgar/Burgas16/index.html
Еднакви графи