Контрольні питання

Що таке: а) неорієнтоване дерево, б) ліс?

Що таке: а) кістякове дерево графу, б) кістяковий ліс графу?

Скільки ребер має дерево порядку n?

Скільки існує різних дерев із заданою множиною вершин, що складається з n елементів?

Яка найменша кількість кінцевих вершин у нетривіальному скінченному дереві?

У яких межах знаходиться число m ребер простого графу порядку n з k компонентами зв’язності?

Задачі та вправи

І. Для заданого графу G визначити, чи є він: а) зв’язним, б) ациклічним, в) не-орієнтованим деревом, д) лісом. Які з графів мають кістякові дерева?

1) G=({1,2,3,4},{(1,2),(1,3),(2,3)}); 2) G=({1,2,3,4},{(1,2),(2,3),(2,4),(3,4)});

3) G=({1,2,3,4},{(2,3),(3,4)}); 4) G=({1,2,3,4},{(1,2),(2,3),(3,4)});

5) G=({1,2,3,4},{(1,2),(2,3),(2,4)}); 6) G=({1,2,3,4},{(1,2),(3,4)});

7) G=({1,2,3,4},{(1,1),(2,3)}); 8) G=({1,2,3,4},{(1,2),(1,3),(2,4),(3,4)}).

ІІ. Побудувати усі кістякові дерева графу ({1,2,3,4,5,6},{(1,2),(1,3),(2,3),(2,4), (3,5),(3,6),(4,6),(5,6)}).

ІІІ. Задана множина V={1,2,3,4,5,6}. Побудувати дерево з множиною вершин V за послідовністю елементів множини V.

1) 1,2,3,4; 2) 1,1,3,3; 3) 1,2,2,1; 4) 1,1,1,1; 5) 1,3,1,3;

6) 1,1,1,4; 7) 4,4,5,6; 8) 1,4,4,6; 9) 2,3,4,2; 10) 6,3,6,6.

ІV. Для заданого дерева Т побудувати послідовність вершин (як показано у доведенні теореми Келі).

1) T=({1,2,3,4,5,6},{(1,2),(1,3),(2,4),(2,5),(2,6)});

2) T=({1,2,3,4,5,6},{(1,2),(2,3),(2,4),(4,5),(4,6)});

3) T=({1,2,3,4,5,6},{(1,2),(1,3),(1,4),(1,5),(1,6)});

4) T=({1,2,3,4,5,6},{(1,3),(2,3),(3,4),(4,5),(4,6)});

5) T=({1,2,3,4,5,6},{(1,2),(2,3),(3,4),(4,5),(5,6)}).

V. Скільки існує дерев: а) з множиною вершин {a,b,c,d,e}; б) з n вершинами, дві з яких є кінцевими; в) порядку n з максимальною кількістю кінцевих вершин?

VІ. На множині вершин {a,b,c,d,e} побудувати усі попарно неізоморфні дере-ва, які мають вершини степеня 2.

VІІ. Нехай G=(V,E) – граф порядку n з m ребрами. Нехай m>(n-1)(n-2)/2. Довести, що G зв’язний.

Лекція 5. Орієнтовані графи та орієнтовані дерева Поняття орієнтованого графу

Орієнтованим графом (орграфом) називається упорядкована пара множин виду (V,E), де V – деяка непорожня множина, EV². Множина V називається множиною вершин орграфу, а її елементи – вершинами; множина E називається множиною дуг орграфу, а її елементи – дугами. Кожна дуга орграфу – це упорядкована пара вершин, перший компонент якої називається початком дуги, а другий – кінцем дуги. Дугу орграфу, початком якої є вершина u, а кінцем – вершина v, будемо позначати (u,v). Дуга (u,v) та вершина u (v) називаються інцидентними, а вершини u та v – суміжними. Оскільки, за визначенням, дуга орграфу є упорядкованою парою вершин, то за умови uv пари (u,v) та (v,u) є різними дугами. Дуга виду (v,v) називається петлею. Дуги е₁ та е₂ орграфу G називаються суміжними, якщо кінець дуги е₁ збігається з початком дуги е₂.

Наприклад, упорядкована пара множин виду ({1,2,3},{(1,2),(3,2),(3,1), (2,3)}) є орграфом, тому що перша множина пари (тобто {1,2,3}) є не порожньою, а друга – це множина упорядкованих пар, побудованих з елементів першої множини. Дуга (1,2) та вершина 1 інцидентні; також інцидентними є дуга (1,2) та вершина 2, дуга (3,2) та вершина 3, дуга (3,2) та вершина, 2, дуга (3,1) та вершина 3, дуга (3,1) та вершина 1, дуга (2,3) та вершина 2, дуга (2,3) та вершина 3. Суміжними є вершини: 1 та 2, 3 та 2, 3 та 1. Дуги (3,1) та (1,2) суміжні. Також суміжними є дуги (1,2) та (2,3), дуги (3,2) та (2,3), дуги (2,3) та (3,2) й дуги (2,3) та (3,1). Пара множин виду ({1,2,3},{(1,2),(3,2),(3,4)}) не є орграфом, оскільки друга множина (тобто {(1,2),(3,2),(3,4)}) містить пару (3,4), другий компонент якої не є елементом множини {1,2,3}.

Так само, як й неорієнтованим графам, орграфам можна надавати імена.

Напівстепенем виходу вершини v орграфу G (позначається on(v)) називається потужність множини дуг орграфу G, для яких вершина v є початком. Напівстепенем заходу вершини v орграфу G (позначається in(v)) називається потужність множини дуг орграфу G, для яких вершина v є кінцем. Степінь вершини v орграфу G позначається n(v) й визначається таким чином: n(v)=on(v)+in(v).

Розглянемо приклад. Нехай задано орграф G=({1,2,3,4},{(1,2),(1,3),(2,3), (3,1),(3,4)}). Обчислимо степені вершин G. Вершина 1 є початком двох дуг ((1,2) та (1,3)) й кінцем однієї дуги (а саме, дуги (3,1)), отже, on(1)=2, in(1)=1, n(1)=on(1)+in(1)=2+1=3. Аналогічно обчислюємо степені інших вершин: on(2)=1, in(2)=1, n(2)=1+1=2; on(3)=2, in(3)=2, n(3)=2+2=4; on(4)=0 (у орграфі G немає жодної дуги, початком якої є вершина 4), in(4)=1, n(4)=0+1=1.

Означення поняття порожнього (повного, скінченного) орграфу, під-графу орграфу, порядку орграфу аналогічне означенню поняття порожнього (повного, скінченного) графу, підграфу графу, порядку графу.

Твердження 10. Для будь-якого скінченного орграфу G=(V,E) порядку n виконується on(v)=in(v).

Доведення. При обчисленні on(v) кожна дуга враховується рівно один раз, отже, on(v)=|E|. Аналогічно in(v)=|E|. Отже, on(v)=in(v). Твердження доведено.

Наслідок. Сума степенів усіх вершин орграфу порядку n є числом парним.

Доведення. n(v)=(on(v)+in(v))=on(v)+in(v)=|E|+|E|=2|E|. Наслідок доведено.