Зображення графів

Визначення графу

Основні поняття і операції

Вступ

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

Теорія графів, як розділ дискретної математики, з успіхом використовується у задачах керування виробництвом і проектування мереж ЕОМ, при розробці сучасних електронних модулів і при проектуванні фізичних систем, при розробці сучасних електронних модулів і при проектуванні фізичних систем, при розв’язуванні задач генетики і вирішенні проблем автоматизованого управління (САПР). Теорія графів є основою математичного забезпечення сучасних систем обробки інформації у прикладній теорії алгоритмів та в інших галузях науки і техніки.

Далі будемо розглядати деякі елементи теорії графів, які мають загальну форму та можуть бути застосовані при дослідженні об’єктів та систем довільної природи.

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

Визначення. Розглянемо множину V, яка складається з точок, частина яких з’єднана між собою. Назвемо V множиною вершин, а об’єкт v Î V - вершиною. Граф

G = G (V)

з множиною вершин V - це деяка сукупність пар вигляду

e = (a, b),

де a, b Î V вказують, які пари вершин з’єднані між собою. Відповідно до геометричних уявлень про граф кожна така пара (a, b) називається ребром графу, а „ а ” і „ b ” – кінцями ребра. З іншого боку, оскільки

e = (a, b) Î V ´ V,

то граф

G (V) Í V ´ V.

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

e = (a, b) = (b, a),

то говорять, що e – неорієнтоване ребро. В протилежному випадку e = (a, b) - орієнтоване ребро, в якому „ а ” – початкова вершина, а „ b ” – кінцева.

Визначення. Якщо e = (a, b), то говорять, що ребро e інцидентне вершинам „ а ” і „ b ”, а вершини „ а ” і „ b ” інцидентні ребру e.

Визначення. Граф G називається неорієнтованим, якщо кожне його ребро є неорієнтованим. Граф G називається орієнтованим, якщо кожне його ребро є орієнтованим.

Рис. 1.

На рис. 1.а, б, в, е зображені деякі неорієнтовані графи, а на рис. 1.г, д – деякі орієнтовані графи (напрями ребер зображені стрілками). Лінії, які відповідають ребрам графів, можуть перетинатись на рисунку, але точки їх перетину не обов’язково повинні бути вершинами графу (див.рис.1.а).

Якщо два ребра інцидентні одній парі вершин, то такі ребра називаються кратними (див.рис.1.б). Ребро, яке з’єднує вершину саму з собою, називають петлею (див.рис.1.д).

Визначення. Граф називається скінченним, якщо кількість ребер в ньому є скінченною (рис.1.а, б, г); інакше граф називають нескінченним (рис.1.е).

Визначення. Вершина графу, не інцидентна жодному ребру, називається ізольованою. Якщо граф складається тільки з ізольованих вершин, то він називається нульграфом (рис.1.в).

Визначення. Будемо говорити, що два графи G і G ’ є ізоморфними, якщо існує така відповідність між множинами їх вершин V і V ’, що у графі G вершини з’єднані між собою тоді і тільки тоді, коли з’єднані між собою відповідні їм вершини у графі G ’. Якщо ребра орієнтовані, то їх напрямки повинні відповідати один одному.

Наприклад:

Твердження. Ізоморфні графи мають однакові властивості.

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

Дата добавления: 2014-11-29