Здавалка
Главная | Обратная связь

Поняття неорієнтованого графу



ПЕРЕДМОВА

У даному навчальному виданні викладено базові поняття теорії графів, які необхідні кожному, хто використовує графові моделі або займається їх розробкою. Подання матеріалу розраховано на початківців: від читача не вимагається спеціальної підготовки у галузі теорії графів. Теоретичні відомості подаються окремими частинами, викладення теоретичного матеріалу супроводжується прикладами; розглядаються типові навчальні задачі та способи їх розв’язання. Після кожної частини є розділ, що містить контрольні питання, які допомагають виділити основне у прочитанному та запам’ятати нові поняття. Для кращого засвоєння матеріалу, формування практичних навичок його застосування, а також для підготовки до контрольних заходів (самостійних, контрольних робіт, усних опитувань) рекомендується виконувати вправи та розв’язувати задачі, подані до кожної частини після контрольних питань.

Крім основного матеріалу, видання містить кілька довідкових розділів, а саме: «Символи та позначення», «Предметний покажчик», «Слова іншомовного походження». Мета включення цих розділів – полегшити користування виданням. У розділі «Символи та позначення» зібрані позначення, які уведені у різних частинах основного тексту; разом з кожним позначенням наведено його тлумачення. Розділ «Предметний покажчик» містить перелік усіх понять теорії графів, означення яких наведено у основному тексті; для кожного поняття дано посилання на сторінку, де це поняття з’являється вперше. У розділі «Слова іншомовного походження» пояснюється походження запозичених з іноземних мов слів-термінів, що зустрічаються у основному тексті.

 


ПОНЯТТЯ НЕОРІЄНТОВАНОГО ГРАФУ. РІЗНОВИДИ, СПОСОБИ ПОДАННЯ ТА ПЕРЕТВОРЕННЯ НЕОРІЄНТОВАНИХ ГРАФІВ

Поняття неорієнтованого графу

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

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

Неорієнтованим графом (або графом) будемо називати упорядковану пару множин виду (V,E), де V¹Æ, Е Í V(2). Множина V називається множиною вершин, а її елементи – вершинами графу; множина Е називається множиною ребер, а її елементи – ребрами графу. Якщо (u,vE, то вершини 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,vE. Зауважимо, що коли вершини u та v суміжні, то й v та u суміжні. Вершина u та ребро (u,v) графу G називаються інцидентними. Ребра е1 та е2 графу 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| множини його вершин. Якщо |VN+, то граф називається графом скінченного порядку, або скінченним. Наприклад, граф G=({a,b,c},{(a,b),(a,c)}) має порядок три, тому що |{a,b,c}|=3; граф (N,{(x,y)| х,уÎN, (xy) – парне число}) є графом нескінченного порядку (нескінченним), бо множина його вершин нескінченна.

Різновиди графів

Граф G=(V,E) називається порожнім, якщо E=Æ. Наприклад, ({a,b,c},Æ) – порожній граф, а граф ({a,b,c},{(a,b),(a,c)}) – ні. Порожній граф з однією вершиною будемо називати тривіальним графом.

Граф називається простим, якщо множина його ребер не містить петель. Наприклад, граф ({a,b,c},{(a,b),(a,c)}) – простий, а граф ({a,b,c}, {(a,b),(c,b),(c,с)}) – ні. Граф з петлями називають псевдографом.

Граф G=(V,E) називається повним, якщо "u,vÎV u та v суміжні. Простий повний скінченний граф порядку n позначається Kn. Наприклад, граф ({a,b,c},{(a,a),(a,b),(a,c),(b,b),(b,c),(c,c)}) є повним; граф ({a,b,c}, {(a,b),(a,c),(b,c)}) – це граф K3 (простий повний граф порядку 3). Граф G=({a,b,c},{(a,b),(a,c)}) не є повним, адже вершини b та c несуміжні, бо граф G не містить ребра (b,c).

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

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

Доведення. Нехай G=(V,E) – простий граф порядку n. Розглянемо суму степенів усіх його вершин S=n(v1)+…+n(vn). Оскільки граф G простий, то кінці кожного ребра даного графу – це різні вершини, отже, кожне ребро (vi,vj) при обчисленні S враховується рівно двічі: при обчисленні степеня вершини vi та при обчисленні степеня вершини vj. Таким чином, S=2×|E|, отже, S є парним числом.

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

Доведення. Нехай G=(V,E) – простий граф порядку n. Подамо суму степенів усіх його вершин S=n(v1)+…+n(vn) у вигляді S=S0+S1, де S0 – сума степенів усіх тих вершин графу G, що мають парні степені, S1 – сума степенів усіх тих вершин графу G, що мають непарні степені. Нехай S1¹0. Оскільки числа S та S0 парні, то звідси випливає, що S1 є числом парним. Кожен доданок у сумі S1 є непарним числом. З парності S1 випливає, що кількість доданків у S1 парна, отже, й кількість вершин непарного степеня графу G парна.

Наслідок 2. Нехай G=(V,E) – простий однорідний граф порядку n степеня р. Тоді принаймні одне з чисел n або р парне.

Доведення. Оскільки граф G однорідний степеня р порядку n, то n(v1)=…=n(vn)=р й S=n(v1)+…+n(vn)=n×р. Оскільки граф G простий, то S – парне число, а тому один з множників добутку n × р є парним числом.

Зауважимо, що коли граф не є простим, сума степенів усіх його вершин не обов’язково є парним числом. Розглянемо, наприклад, граф ({a,b,c},{(a,a),(a,b),(a,c),(b,c)}), що не є простим, й обчислимо суму степенів S усіх його вершин. Маємо: S=n(a)+n(b)+n(c)=3+2+2=7, тобто S непарне.

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.