Лекція 6. Графи

сім мостів і кожним мостом пройти рівно один раз. На

острів не можна було потрапити інакше як через міст, і кожен з мостів мав бути пройденим за один раз (тобто не можна було пройти на середину мосту і повернутися назад, а потім з іншого берега пройти другу половину). Ейлер довів, що розв'язку не існує.

непорожньої множини вершин V та множини ребер E.

Орієнтований граф

(орграф) - це граф, ребра якого мають напрям.
Ребра орграфа називаються дугами.

які з’єднують точки.

Кількість ребер, інцидентних до певної вершини x, називається

степенем цієї вершини і позначається d(x).

Вершина, в якої степінь дорівнює 0, називається ізольованою. Вершини, які мають степінь 1, називаються висячими, або кінцевими .

Петлями називають ребра, які мають збіжні кінці.

Граф, який не має ребер (U = ∅), називається порожнім. Усі вершинипорожнього графа є ізольовані.

ребром, називається повним і позначається Kn.
Кількість ребер в повному графі

дорівнює

Граф, який може бути зображено на площині (без перетину ребер), називається планарним.

ребер.
Д о в е д е н н я
Кожне ребро

двічі входить до суми, звідки й випливає твердження.

Теорема 2. У кожному графі число вершин, які мають непарний степінь, є парне.
Д о в е д е н н я
Нехай X1 ⊆ X – множина вершин непарного степеня; X2 ⊆ X – множина вершин парного степеня. Зазначимо, що X = X1 ∪ X2; X1 ∩ X2 = ∅.

з петлями.
Граф, що не містить петель і кратних ребер,

називається звичайним, або простим графом.

Підграф називають власним, якщо він відмінний від самого графа.
Граф

G=(X,V) називається остовним підграфом графа G=(X,V),якщо X =X та V ⊆V.

V2 так, що ніякі дві вершини, що належать тій самій

підмножині, не суміжні, називається дводольним (графом Кеніга) і позначається Bmn (m=|V1|, n=|V2|, m+n=|V|).

B33

Граф, вершини якого можна розбити на n непересічних підмножини так, що ніякі дві вершини, що належать одній підмножині, не суміжні, називається n-дольним.

Тридольний граф

графами існує взаємо-однозначне відображення j: G1

відповідність між ребрами (дугами) графів.

називають граф G=(X,V), якщо його ребро (xi,xj) входить в V

тоді і тільки тоді, коли воно не входить в V. Іншими словами, дві вершини xi і xj суміжні в G, якщо вони не суміжні в G.

G = (X,V)

G-xi – граф, що отриманий видаленням з графа G вершини

xі та ребер інциндентних цій вершині.

G = (X,V)

3. Видалення ребер.
Нехай li – ребро графу G = (X,V). Тоді G-(li) – підграф графу G, який отримано після викидання ребра li.

кінцевих вершин. Граф G називають стягненим до графу Н, якщо

Н можна отримати з G послідовністю стягувань .

5. Замкнення або ототожнювання.
Кажуть, що пара вершин графу G xi та xj замикаються (ототожнюються), якщо вони замінюються новою вершиною, всі ребра графу G інциндентні xi та xj, стають інциндентними новій вершині.

G2, позначається G1G2, є граф G3 = (X1X2, V1V2) множина

його вершин є об’єднанням X1 та X2, а множина його ребер є об’єднанням V1 та V2 .

G1

G1G2

G3 = (X1X2,V1V2), тобто множина його вершин складається лише з

тих вершин, які є одночасно в G1 та G2, а множина ребер G3 складається з ребер, які одночасно присутні в G1 та G2 .

G1

G1G2

позначається G1G2, являє собою граф G3, який складається з ребер,

що присутні або в G1, або в G2, але не в обох одночасно.

G1

G1G2