Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

У багатьох випадках не має особливого значення, як зобразити граф у вигляді рисунка на площині (діаграми), оскільки ізоморфні графи подібні за своєю структурою і містять ту саму інформацію. Однак існують ситуації, коли необхідно, щоб зображення графа на площині задовольняло певні умови. Наприклад, якщо граф є моделлю деякої електронної схеми або транспортної мережі, де вершинами є окремі елементи схеми або станції, а ребрами, відповідно, - електричні провідники і шляхи, то бажано так розташувати ці ребра на площині, щоб уникнути перетинів.

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

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

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

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

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

       
   
 
 

 

 


а) б)

Рис.

 

При дослідженні плоских графів особливе місце займають графи K5 i K3,3, зображені на рис.

 

       
 
   
 

 


 

K5 K3,3

Рис.

 

Граф K3,3 виникає із задачі про три хати і три криниці.

 

Теорема. Графи K5 i K3,3 не є планарними.

 

Значення графів K5 i K3,3 полягає в тому, що вони є "єдиними" суттєво непланарними графами. Всі інші непланарні графи містять у собі підграфи "подібні" до K5 або K3,3. Характер цієї подібності розкривається за допомогою таких понять.

Елементарним стягуванням графа G =(V,E ) називається вилучення в графі G деякого ребра (vi,vjE і злиття вершин vi i vj в одну вершину v, причому v інцидентна всім тим відмінним від (vi,vj) ребрам графа G, які були інцидентні або vi , або vj.

Кажуть, що граф G стягується до графа G ¢, якщо G ¢ можна отримати з G за допомогою послідовності елементарних стягувань.

Приклад . На рис. зображено графи G i G ¢, при цьому G стягується до G ¢.

 

       
   
 

 

 


G G ¢

Рис.

 

Наведемо без доведення важливу теорему теорії графів.

Теорема (теорема Куратовського). Граф G є планарним тоді і тільки тоді, коли він не містить підграфів, що стягуються до K5 або K3,3.

 


Читайте також:

  1. Henri Matisse- Биография художника на английском.
  2. Биография населенного мира
  3. Двочасткові графи
  4. ДЕМОГРАФИЯ
  5. Дробот В. Изучение биографии писателя в школе.- К., 1988.
  6. Електронно-променеві осцилографи
  7. Електронно-променеві осцилографи
  8. Лекция 1. Векторная графика. Macromedia Flash MX Инструменты и технологии рисования во Flash
  9. Лекція № 13. ОРІЄНТОВАНІ ГРАФИ
  10. ЛИТОЛОГО-СТРАТИГРАФИЧЕСКИИ МЕТОД РАСЧЛЕНЕНИЯ
  11. Світлопроменеві (шлейфові) осцилографи




Переглядів: 1821

<== попередня сторінка | наступна сторінка ==>
Двочасткові графи | Розфарбування графів

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.004 сек.