Въпрос 2

Графи. Дървета. Обхождане на графи.

Анотация

Дефиниции за краен ориентиран (мулти)граф и краен неориентиран (мулти)граф.

Дефиниции за маршрут (контур) в ориентиран мултиграф и път (цикъл) в неориентиран мултиграф.

Свързаност и свързани компоненти на граф.

Дефиниция на дърво и кореново дърво. Доказателство, че всяко кореново дърво е дърво и |V|=|E|+1.

Покриващо дърво на граф. Обхождане на граф в ширина и дълбочина.

Ойлерови обхождания на мултиграф. Теореми за съществуване на Ойлеров цикъл (с доказателство) и Ойлеров път.

Примерни задачи:

1. Да се построи покриващо дърво на зададен граф – в ширина или дълбочина.
2. Да се построи Ойлеров цикъл (или път) в зададен мултиграф или да се докаже, че такъв цикъл (или път) не съществува.
3. Да се разбие множеството на ребрата на неориентиран граф на минимален брой пътища, никои два от които нямат общо ребро.

Литература: [10].