Презентация на тему Графи. Основні поняття і визначення

пройти всі сім мостів і кожним мостом пройти рівно

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

це сукупність непорожньої множини вершин V та множини ребер

E.

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

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

Кількість ребер, інцидентних до певної

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

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

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

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

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

в повному графі дорівнює

 

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

подвоєній кількості ребер.
Д о в е д е н

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

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

 

 

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

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

х1⊂X, v1⊂V. Підграф називають власним, якщо він відмінний від

самого графа.

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

V1 і V2 так, що ніякі дві вершини, що

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

B33

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

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

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

E1

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

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

G = (X,V)

 

= (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, стають інциндентними новій вершині.

G1 та 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