Граф називається плоским, якщо його можна накреслити на площині так, щоб жодне ребро не перетиналося.
приклад: Графік, показаний на рис, є плоским графом.
машинопис для кожного
Область графіка: Розглянемо планарний граф G=(V,E). Область визначається як область площини, яка обмежена ребрами та не може бути поділена далі. Планарний граф поділяє плани на одну або кілька областей. Одна з цих областей буде нескінченною.
Кінцевий регіон: Якщо площа області скінченна, то цю область називають скінченною.
Нескінченна область: Якщо площа області нескінченна, то ця область називається нескінченною. Плоский граф має лише одну нескінченну область.
приклад: Розглянемо графік, зображений на рис. Визначте кількість областей, кінцеву область і нескінченну область.
рішення: На наведеному вище графіку є п’ять регіонів, тобто r1,р2,р3,р4,р5.
На графіку є чотири кінцеві області, тобто r2,р3,р4,р5.
Існує лише одна кінцева область, тобто r1
Властивості плоских графів:
- Якщо зв’язний плоский граф G має e ребер і r областей, то r ≦
Це є. - Якщо зв’язний плоский граф G має e ребер, v вершин і r областей, то v-e+r=2.
- Якщо зв’язний плоский граф G має e ребер і v вершин, то 3v-e≧6.
- Повний графік Кпє плоскою тоді і тільки тоді, коли n<5.< li>
- Повний дводольний граф Kмнє плоским тоді і тільки тоді, коли m3.
приклад: Доведіть, що повний граф К4є плоским.
рішення: Повний граф К4містить 4 вершини і 6 ребер.
Ми знаємо, що для зв’язного плоского графа 3v-e≧6. Отже, для K4, маємо 3x4-6=6, що задовольняє властивість (3).
росомаха проти борсука
Таким чином К4є плоским графом. Отже, доведено.
Неплоский графік:
Граф називається неплоским, якщо його не можна накреслити на площині так, щоб жодне ребро не перетиналося.
приклад: Графіки, показані на рис, є неплоскими.
Ці графіки не можна накреслити на площині так, щоб жодне ребро не перетиналося, тому вони є неплоскими графами.
Властивості неплоських графів:
Граф неплоский тоді і тільки тоді, коли він містить підграф, гомеоморфний K5або К3.3
бінарне дерево
Приклад 1: Покажіть, що К5є неплощинним.
рішення: Повний граф К5містить 5 вершин і 10 ребер.
Тепер для зв’язного плоского графа 3v-e≧6.
Отже, для К5, маємо 3 x 5-10=5 (що не задовольняє властивість 3, оскільки має бути більше або дорівнювати 6).
Таким чином, К5є неплощим графом.
Приклад 2: Покажіть, що графіки, зображені на рис. 1, є неплоскими, знайшовши підграф, гомеоморфний K5або К3.3.
рішення: Якщо прибрати краї (V1,IN4),(IN3,IN4) і (В5,IN4) графік G1, стає гомеоморфним K5.Отже, він неплоский.
Якщо видалити ребро V2,V7) графік G2стає гомеоморфним К3.3.Отже, вона неплоска.
Розфарбування графіка:
Припустимо, що G= (V,E) — граф без кратних ребер. Розфарбовування вершин G — це призначення кольорів вершинам G таким чином, що сусідні вершини мають різні кольори. Граф G є M-розфарбовуваним, якщо існує розфарбування G, яке використовує M-кольори.
fmovies Індія
Правильне фарбування: Розмальовка є правильною, якщо будь-які дві сусідні вершини u і v мають різні кольори, інакше вона називається неправильною.
приклад: Розгляньте наступний графік і розфарбуйте C={r, w, b, y}. Розфарбуйте графік належним чином, використовуючи всі кольори або меншу кількість кольорів.
Графік, показаний на рис., є мінімум 3-розфарбованим, отже x(G)=3
рішення: На рис. зображено графік, правильно розфарбований усіма чотирма кольорами.
На рис. зображено графік, правильно розфарбований трьома кольорами.
Хроматичне число G: Мінімальна кількість кольорів, необхідних для правильного розфарбування графа G, називається хроматичним числом G і позначається x(G).
приклад: Хроматичне число Допє п.
рішення: Розмальовка Допможна побудувати з використанням n кольорів, призначаючи різні кольори кожній вершині. Жодним двом вершинам не можна призначити однакові кольори, оскільки кожні дві вершини цього графа є суміжними. Звідси хроматичне число Кп=n.
Застосування розфарбовування графів
Деякі застосування фарбування графіків включають:
- Зареєструвати розподіл
- Розмальовка карти
- Перевірка дводольного графа
- Присвоєння мобільних радіочастот
- Складання розкладу та ін.
Сформулюйте та доведіть теорему рукостискання.
Теорема рукостискання: Сума ступенів усіх вершин у графі G дорівнює подвоєній кількості ребер у графі.
Математично це можна сформулювати так:
∑v∈Vdeg(v)=2e
Доказ: Нехай G = (V, E) — граф, де V = {v1,в2, . . . . . . . . . .} — множина вершин і E = {e1,Це є2. . . . . . . . . .} — множина ребер. Ми знаємо, що кожне ребро лежить між двома вершинами, тому воно забезпечує ступінь один для кожної вершини. Отже, кожне ребро вносить другий ступінь для графа. Отже, сума ступенів усіх вершин дорівнює подвоєній кількості ребер у G.
Отже, ∑v∈Vdeg(v)=2e
цикл for в java