ебра не перетиналися ніде, крім вершин, називаються плоским планарним.
Розглянемо граф з п'ятьма вершинами, попарно сполученими один з одним (ріс.1.3.15). Тут ребра графа перетинаються. Неможливо його зобразити так, щоб пересічний не було, як неможливо виконати наміри трьох осіб, описаних Льюсу Керроллом в одній з завдань.
Завдання. Вони жили в трьох будиночках, неподалік від них знаходилися три криниці: один з водою, інший з маслом, а третій з повидлом, і ходили до них по стежках (рис. 1.3.15). Одного разу ці люди пересварилися і вирішили провести стежки від своїх будинків до криниць так, щоб ці стежки не перетиналися.
Графи, зображені на малюнку 1.3.15, як виявилося, відіграють вирішальну роль при визначення для кожного графа - чи є він плоским, тобто чи може він бути зображений на площині без перетину його ребер. Польський математик Г. Куратовський і академік Л. С. Понтрягин незалежно довели.
ріс.1.3.15
Теорема Понтрягіна - Куратовского: Граф є плоским тоді і тільки тоді, коли він не містить (в топологічному сенсі) графа з шістьма вершинами типу «будиночки-колодязі» і повного графа з п'ятьма вершинами (ріс.1.3.15) [22 ]. (В основному використовується старовинних задач про будинках і колодязях, суть якої зводиться до з'ясування питання - чи є розглянутий граф плоским чи ні (ріс.1.3.16).
ріс.1.3.16
д) Орієнтовані графи.
Існують значні класи практичних завдань, які вирішити за допомогою раніше розглянутих типів графів неможливо. Так, наприклад, схема доріг і площ міста зображується за допомогою плоского графа. Але якщо потрібно цією схемою скористатися з метою проїзду по місту на автомашині, а рух на окремих (або на всіх) вулицях одностороннє?
Граф, на ребрах якого розставлені стрілки, називається орієнтованим.
Ступенем виходу вершини орієнтованого графа називається число ребер, для яких ця вершина є початком (число ребер, «виходять» з вершини). Ступенем входу вершини орієнтованого графа називається число ребер, для яких ця вершина є кінцем (число ребер, «вхідних» в вершину).
ріс.1.3.17
Так, на малюнку 1.3.17 зображений орієнтований граф АБВГД. Ступені входу і виходу деяких його вершин такі:
ст. вх. А=2, ст. вих. А=1
ст. вх. В=2, ст. вих. В=0
ст. вх. Д=1, ст. вих. Д=3
Шляхом, в орієнтованому графі від вершини А1 до вершини An називається послідовність орієнтованих ребер,, ... в якій кінець кожного попереднього ребра збігається з початком наступного і кожне ребро зустрічається в цій послідовності тільки один раз. На нижче наведеному малюнку показані приклади шляхів в орієнтованому графі. Причому, перші два шляху- прості - жодна з вершин не міститься в ньому більше одного разу. Третій шлях не є простим, т. К. Через вершину Г шлях «проходив» двічі (ріс.1.3.18).
ріс.1.3.18
Орієнтованим циклом називається замкнутий шлях в орієнтованому графі.
На попередньому малюнку наведені приклади орієнтованих циклів в останніх двох графах. Цикл, як і будь-який інший шлях в графі, має довжину, яка визначається числом ребер в цьому шляху.
ріс.1.3.19
Так, на малюнку 1.3.19 шляху від А до Д можуть бути різні і мати різну довжину. Перший шлях має довжину 2, другий - 3, а третій - 4. Довжина «найкоротшого шляху» між двома вершинами називається відстанню між ними. Так відстань між вершинами А і Д на графі малюнка 1.3.19 одно 2; записують так: S (АТ)=2.
ріс.1.3.20
Якщо в орієнтованому графі не можна «пройти» від однієї вершини до іншої, то відстань між ними називають нескінченним (позначають значком нескінченності). Так, відстань між вершинами Б і Д графа, представленого на малюнку 1.3.20 нескінченно:
Орієнтовані графи в економіці активно використовуються в мережевому плануванні, у математиці - в теорії ігор, теорії множин; при вирішенні багатьох завдань, зокрема, комбінаторних [3].
Виникає питання: чи так потрібні були графи в розібраних задачах? Хіба не можна прийти до вирішення суто логічним шляхом? Так можна. Але графи надали умовам наочність, спростили рішення і виявили схожість завдань, перетворивши два завдання в одну, а це вже не так уже й мало. А тепер уявіть собі завдання, графи яких мають 100 або більше вершин. А адже саме такі завдання доводиться вирішувати сучасним інженерам і економістам. Тут без графів не обійтися.
Наведемо приклади додатків теорії графів. «Транспортні» завдання, в яких вершинами графа є пункти, а ребра - дороги (автомобільні, залізниці та ін.) Або інші транспортні (наприклад, авіаційні) маршрути. Також прикладами графів генеалогічне дерево (де вершини - члени роду, а зв'язують їх відрізки - відносини спорідненості), класифікація геометричних об'єктів [4,5,8,18].
Класифікація геометричних об'єкт...
