Вершини, ребра (дуги), графи - студопедія

Сукупність безлічі вершин V і безлічі зв'язків Е між ними називається графом і позначається G (V. E).

На рис. 2.1 показаний приклад графа G (4,6), де позначено:

n = | V | = 4 - число вершин графа G (4,6),

m = | E | = 6 - число ребер графа G (4,6).

E - це відображення V в V (E. VV).

Іноді безліч E називають сімейством зв'язків, так як в E можуть входити спрямовані і ненаправлення зв'язку, петлі і всі вони можуть бути кратними, тоді як в теорії множин однакові елементи представляються одним елементом.

Як інший приклад на рис. 2.2 показано сімейство графів на чотирьох вершинах.

Зверніть увагу на загальноприйняті позначення деяких графів:

K4 - повний граф, в ньому кожна вершина має зв'язок з усіма іншими вершинами.

У загальному випадку ці типи графів позначаються так:

Звернемо увагу на граф C4. Цей граф можна представити і так, як показано на рис. 2.3. Такий граф позначається K2,2 і називається повним дводольним графом.

У дводольному графі безліч вершин V розбито на два підмножини X і Y таких, що між вершинами всередині кожного з них немає зв'язків. Число ребер у повному дводольному графі m = n1n2. де n1 = | X |, n2 = | Y |, n = n1 + n2.

Якщо зв'язок має напрямок, то вона називається дугою, в іншому випадку - ребром. (Графи з дугами і ребрами показані на рис. 2.4.)

При необхідності конкретна дуга (ребро) позначається або власним ім'ям, або парою вершин в круглих (прямих) дужках e = (v1, v2) - дуга e, (e = [v1, v2] - ребро e).

Граф, у якого всі зв'язки є ребрами, називається неорієнтованим графом або скорочено неорграфом (рис. 2.4, а).

Граф з дугами називається орієнтованим графом або Орграф (рис. 2.4, б).

Ребро (дуга), обидва кінці якого пов'язані з однією і тією ж вершиною, називається петлею (рис. 2.5).

Якщо у графа існують кратні ребра, тобто кілька ребер, що з'єднують одну й ту ж саму пару вершин, то такий граф називається мультиграфом. Якщо все ребра мультиграфом мають однакову кратність k. то такий граф називається k-кратної або просто k -графом. На рис. 2.6 показаний мультіграф G (6,20):

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

Дві вершини називаються суміжними, якщо вони з'єднуються деяким ребром (дугою), і два різні ребра (дуги) суміжні, якщо вони мають загальну вершину. На рис. 2.8 у графа G (3,3) суміжні вершини a і b; a і c; b і c. а також суміжні дуги e2 і e3. суміжні ребро e1 і дуга e2. суміжні ребро e1 і дуга e3.

Дві вершини називаються суміжними, якщо вони з'єднуються деяким ребром (дугою), і два різні ребра (дуги) суміжні, якщо вони мають загальну вершину. На рис. 2.8 у графа G (3,3) суміжні вершини a і b; a і c; b і c. а також суміжні дуги e2 і e3. суміжні ребро e1 і дуга e2. суміжні ребро e1 і дуга e3.

Вершина х инцидентна ребру (дузі) е. Якщо вона є початком або кінцем ребра (дуги). На рис. 2.8 вершини a і b інцидентні ребру e1. вершини b і c інцидентні дузі e2.

Дуга (ребро) е инцидентна вершині x. якщо вона виходить з цієї вершини або входить в неї. На рис. 2.8 дуга e2 инцидентна вершин b і c.