азивається інцідентним і навпаки.
Ребро, в свою чергу, з'єднує ці вершини. Дві кінцеві вершини одного і того ж ребра називаються сусідніми .
Однак, існує і такий варіант, при якому дві вершини з'єднують два ребра. Якщо в графі існує таке з'єднання, то говорять, що в графі допускаються кратні ребра . Граф з кратними ребрами називають мультиграфом .
Також, ребро, що з'єднує вершину з собою, тобто ребро, яке виходить і входить в одну й ту ж вершину називають петлею .
Комбінуючи перерахованого вище можна отримати різні варіанти визначення поняття графа. Найчастіше зустрічаються графи неорієнтовані графи без петель і кратних ребер. Такі графи називаються звичайним графом .
Подграфом графа G називається граф, всі вершини і дуги якого містяться серед вершин і дуг графа G. Всякий подграф може бути отриманий шляхом видаленням деяких вершин або ребер.
Сам граф по відношенню до своїх подграфа називається надграфом (суграфом або суперграфом). На Рис. 1.2 представлений подграф графа, наведеного вище ( Рис. 1.1 м. ).
алгоритм граф матриця
Існує також поняття порожній граф, граф, який не має ребер і вершин.
Повним називається граф, в якому дві вершини суміжні.
2. Застосування графів
Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або знову проектовані будинки, споруди, квартали і т.п. розглядаються як вершини, а що з'єднують їх дороги, інженерні мережі, лінії електропередачі і т.п.- Як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.
Основні сфери застосування теорії графів:
У хімії (для опису структур, шляхів складних реакцій, правило фаз також може бути інтерпретоване як задача теорії графів); комп'ютерна хімія - порівняно молода область хімії, заснована на застосуванні теорії графів. Теорія графів являє собою математичну основу хемоінформатики. Теорія графів дозволяє точно визначити число теоретично можливих ізомерів у вуглеводнів та інших органічних сполук;
В інформатиці і програмуванні (граф-схема алгоритму);
В комунікаційних і транспортних системах. Зокрема, для маршрутизації даних в Інтернеті;
В економіці;
У логістиці;
У схемотехніці (топологія межсоединений елементів на друкованій платі або мікросхемі являє собою граф або гіперграфах).
Виділяють особливий вид графа, дерево. Дерево - це зв'язний ациклічний граф. Зв'язність означає наявність шляхів між будь-якою парою вершин, ациклічності - відсутність циклів і те, що між парами в...
