На головну

Елементи теорії графів

  1. III. Артилерійський ПОСТРІЛ І ЙОГО ЕЛЕМЕНТИ
  2. III.4.3) Види і елементи провини.
  3. XI. Пристосування ТА ІНШІ ЕЛЕМЕНТИ, властивості. Здібностей та обдарувань АРТИСТА
  4. XII. Теорії суспільного розвитку в 20 столітті.
  5. Z4.3. ТЕОРІЇ ЛІДЕРСТВА І СТИЛІ КЕРІВНИЦТВА
  6. Абсолютизм (абсолютно-гетерономний, абсолютно-автономні, інтуїтивні теорії)
  7. Автори теорії.

Початок теорії графів можна віднести до 1736 року, коли Л. Ейлер вирішив задачу про кенігсберзькими мостах. У місті Кенігсберзі (нині Калінінград) є два острови, з'єднані сім'ю мостами з берегами річки Преголя і один з одним. Завдання полягало в тому, щоб знайти маршрут, що проходить всі чотири частини міста, що починається і закінчується в будь-який з його частин і проходить рівно один раз по кожному з мостів. Ейлер не тільки вирішив цю задачу, але і знайшов критерій існування в графі спеціального маршруту (ейлерова циклу, як тепер його називають). Однак цей результат більш ста років залишався єдиним результатом теорії графів. Лише в середині XIX століття інженер-електрик Г. Кірхгоф розробив теорію дерев для дослідження електричних ланцюгів, а математик А. Келі в зв'язку з описом будови вуглеводнів вирішив перечислительного завдання для трьох типів дерев. До цього ж періоду відноситься поява знаменитої проблеми чотирьох фарб.

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

Основні поняття і визначення

Визначення. Нехай дано 2 безлічі: V = {v1, v2, ...} І
 E = {(vi, vj) / Vi, vj  V}. Тоді пара (V, E) є граф, Де V - безліч вершин, E - безліч ребер.

Ми будемо розглядати такі графи, в яких безлічі V і E кінцеві, такі графи називаються кінцевими.

Всі графи діляться на 2 групи:

1) орієнтовані графи або орграф (коли важливий порядок входження вершини в пару, яка визначає ребро);

2) неорієнтовані графи (коли порядок входження вершини в пару не важливий).

Зауваження.За замовчуванням граф неорієнтований.

Визначення.ребро виду  називається петлею.

Визначення.ребра виду ,  , де  , називаються кратними.

Визначення.Нехай | V | = P, | E | = Q, тоді граф, що містить p вершин і q ребер, називається (p, q) -графом.

Якщо G - (p, q) -граф, то p (G) - число вершин у графі G, q (G) - число ребер в графі G.

Визначення.вершини и  називаються суміжними, якщо  ребро  з E виду  (якщо  ребро, яке їх з'єднує). У цьому випадку також кажуть, що вершина  і ребро інцідентни один одному.

 



Попередня   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   Наступна

Лемма про немонотонної функції | передповний клас функцій алгебри логіки | Подання про результати Посту | Завдання для самостійної роботи | Схеми з функціональних елементів | Визначення схем з функціональних елементів | Найпростіші методи синтезу | метод Шеннона | Спеціальне подання функцій | метод синтезу |

© um.co.ua - учбові матеріали та реферати