UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПлоскі та планарні графи (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2816
Скачало301
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Плоскі та планарні графи

 

У багатьох випадках не має особливого значення, як зобразити граф у

вигляді рисунка на площині (діаграми), оскільки ізоморфні графи подібні

за своєю структурою і містять ту саму інформацію. Однак існують

ситуації, коли необхідно, щоб зображення графа на площині задовольняло

певні умови. Наприклад, якщо граф є моделлю деякої електронної схеми або

транспортної мережі, де вершинами є окремі елементи схеми або станції, а

ребрами, відповідно, ( електричні провідники і шляхи, то бажано так

розташувати ці ребра на площині, щоб уникнути перетинів.

 

Таким чином виникає поняття плоского графа.

 

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

так, що лінії, які відповідають ребрам графа, не перетинаються (тобто

мають спільні точки тільки у вершинах графа). Таке зображення

називається плоскою картою графа.

 

Граф називають планарним, якщо він ізоморфний деякому плоскому графу.

 

Наприклад, граф, зображений на рис.3.7,а, планарний, оскільки він

ізоморфний графу, зображеному поруч. Простий цикл, дерево і ліс ( це

також планарні графи.

 

Очевидними є такі твердження.

 

Лема 3.4. 1). Будь-який підграф планарного графа є планарним.

 

2). Граф є планарним тоді і тільки тоді, коли кожна його зв’язна

компонента ( планарний граф.

 

Про планарні графи кажуть, що вони укладаються на площині або мають

плоске укладання.

 

а)

б)

 

Рис.3.7

 

Жордановою кривою будемо називати неперервну лінію, яка не перетинає

сама себе. Гранню плоского графа назвемо множину точок площини, кожна

пара яких може бути з’єднана жордановою кривою, що не перетинає ребер

графа. Межею грані будемо вважати замкнений маршрут, що обмежує цю

грань.

 

На рис.3.8 зображено плоский граф із п’ятьма гранями.

 

Рис.3.8

 

Отже, плоский граф розбиває всю множину точок площини на грані так, що

кожна точка належить деякій грані. Відзначимо, що плоский граф має одну,

причому єдину, необмежену грань (на рис.3.8 це грань 5). Таку грань

будемо називати зовнішньою, а всі інші ( внутрішніми гранями.

 

Множину граней плоского графа позначатимемо через P.

 

Степенем грані r називатимемо довжину циклічного шляху, що обмежує грань

r (тобто довжину межі грані r ); позначається (r.

 

Для плоского графа на рис.3.8 {v3,(v3,v2),v2,(v2,v4),v4,(v4,v3),v3} (

циклічний шлях для грані 1,

{v2,(v2,v5),v5,(v5,v7),v7,(v7,v5),v5,(v5,v8),

v8,(v8,v10),v10,(v10,v6),v6,(v6,v2),v2} ( циклічний шлях для грані 3.

Отже, (1=3 i (3=7.

 

(r=2 |E |.

 

Доведення. Справді, кожне ребро плоского графа або розділяє дві різні

грані, або знаходиться всередині однієї грані. Отже, кожне ребро графа G

або входить у межі тільки двох граней, або є елементом межі лише однієї

грані, але при циклічному обході цієї грані таке ребро проходиться

двічі. Тобто кожне ребро плоского графа вносить у розглядувану суму дві

одиниці.

 

Теорема 3.13. (теорема Ейлера). Для будь-якого зв’язного плоского графа

G =(V,E ) виконується рівність

 

|V |(|E |+|P |=2.

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ