Лекція 1. Поняття неорієнтованого графу. Різновиди, способи подання та перетворення неорієнтованих графів Поняття неорієнтованого графу

Неупорядкованою парою об’єктів х та y (позначається (x,y)) будемо називати сукупність двох об’єктів (не обов’язково різних), порядок розташування яких значення не має, тобто неупорядкована пара виду (y,х) – це те саме, що й неупорядкована пара (x,y). Поняття неупорядкованої пари можна поширити й розглядати для будь-якого цілого додатного числа n2 неупорядковану n-ку об’єктів х₁,…,х_n (позначається (х₁,…,х_n)).

Нехай V – деяка множина. Позначимо через V⁽²⁾ множину усіх неупоряд-кованих пар елементів множини V. Наприклад, якщо V={a,b,c}, то V⁽²⁾={(a,a), (a,b),(a,c),(b,b),(b,c),(c,c)}.

Неорієнтованим графом (або графом) будемо називати упорядковану пару множин виду (V,E), де V, Е  V⁽²⁾. Множина V називається множиною вершин, а її елементи – вершинами графу; множина Е називається множи-ною ребер, а її елементи – ребрами графу. Якщо (u,v)E, то вершини u та v називаються кінцями ребра (u,v). Ребро виду (u,u) називається петлею.

Прикладом графу є пара множин ({a,b,c},{(a,b),(c,b),(c,a)}), оскільки перша множина не порожня, а друга складається з неупорядкованих пар елементів першої множини. Пара множин ({a,b,c},{(b,a),(a,c)}) також є графом. Множини {a,b,c} та {(b,a),(a,е)} не утворюють граф, тому що друга множина містить пару (а,е), що складається з об’єктів а та е, але е{a,b,c}.

Граф може мати ім’я. Зазвичай імена графів позначаються великими латинськими літерами, що можуть мати індекси. На письмі ім’я графу розміщується перед графом, й між ними ставиться знак «=». Наприклад, запис G=({a,b,c},{(a,b),(a,c)}) означає, що графу ({a,b,c},{(a,b),(a,c)}) дано ім’я G. Ім’я графу можна використовувати замість самого графу. Одному й тому самому графові можна дати кілька імен.

Нехай G=(V,E) – граф, u,vV. Назвемо вершини u та v суміжними, якщо (u,v)E. Зауважимо, що коли вершини u та v суміжні, то й v та u суміжні. Вершина u та ребро (u,v) графа G називаються інцидентними. Ребра е₁ та е₂ графу G, що мають спільний кінець, назвемо суміжними.

Степенем вершини u графу G (позначається n(u)) називається потужність множини усіх інцидентних вершині u ребер. Вершина степеня 0 називається ізольованою. Вершина степеня 1 називається кінцевою. Кінцевим ребром графу назвемо ребро, інцидентне кінцевій вершині.

Нехай, наприклад, G=({a,b,c},{(a,b),(a,c)}). Вершини a та b суміжні, адже граф G має ребро (a,b), вершини a та c також суміжні, а вершини b та c несуміжні; визначимо степені вершин графу G: n(a)=2, оскільки у графі G є два ребра, що інцидентні вершині a, n(b)=1, n(c)=1. Вершини b та c є кінцевими. Граф G не має ізольованих вершин (степені усіх його вершин додатні). Ребра (a,b) та (a,c) суміжні, бо мають спільний кінець, яким є вершина а.

Порядком графу G=(V,E) називається потужність |V| множини його вершин. Якщо |V|N⁺, то граф називається графом скінченного порядку, або скінченним. Наприклад, граф G=({a,b,c},{(a,b),(a,c)}) має порядок три, тому що |{a,b,c}|=3; граф (N,{(x,y)| х,уN, (x–y) – парне число}) є графом нескінченного порядку (нескінченним), бо множина його вершин нескінченна.