Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа




Скачати 216.87 Kb.
НазваЛекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа
Сторінка1/4
Дата конвертації11.08.2013
Розмір216.87 Kb.
ТипЛекція
skaz.com.ua > Математика > Лекція
  1   2   3   4

Лекція №14. Визначення графа як абстрактного математичного поняття



Визначення (p,q) графа, (1,0) графа

Ізоморфність графів

Поняття підграфа і надграфа

Маршрут, ланцюг, цикл в графі
Граф складається з скінченої непустої множини , яка містить вершин і заданої множини , яка має невпорядкованих пар різних вершин з . Будь-яку пару вершин в називають ребром графа і говорять, що з’єднує вершину з вершиною . Будемо писати і говорити, що і суміжні вершини; вершина і ребро інцидентні. Якщо два різних ребра інцидентні одній і тій самій вершині, то вони називаються суміжними. Граф з вершинами і ребрами називається -графом. граф називається тривіальним. Граф з даними ребрами є деяка підмножина добутку . Якщо для ребра виконується умова , то неорієнтоване ребро, якщо ж порядок існує, то ребро називається орієнтованим. Орієнтовані ребра позначаються стрілкою.

Граф називається неорієнтованим, якщо неорієнтоване будь-яке ребро графа і орієнтованим, якщо орієнтовані усі його ребра. Змішані графи мають як орієнтовані так і неорієнтовані ребра.

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

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

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

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

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

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

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

Вершина, яка не інцидентна жодному ребру називається ізольованою. Граф, який складається тільки з ізольованих вершин називається нуль-графом.

^ Повний граф – це граф, у якому ребра - це усі можливі пари вершин.

Інваріант графа - це число, яке пов’язане з і яке приймає одне і те саме значення на будь-якому графі, ізоморфному . Числа і називаються інваріантами графа.

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

^ Остовний підграф – це підграф , який містить усі вершини графа .

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



породжений, остовний, але

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



Маршрут - це послідовність вершин і ребер . Ця послідовність починається і закінчується вершиною, будь-яке ребро послідовності інцидентне двом вершинам, одна з яких безпосередньо передує йому, а друга безпосередньо слідує за ним. Вказаний маршрут з’єднує вершини і і його можна позначити . Маршрут називається замкненим, якщо і відкритим у противному разі. Маршрут називається ланцюгом, якщо усі його ребра різні, простим ланцюгом, якщо всі його вершини (а отже, і ребра) різні. Замкнений ланцюг називається циклом. Замкнений маршрут називається простим циклом, якщо усі його -вершини різні. Маршрут нетривіальний, якщо він містить хоча б одне ребро. Нуль - маршрут не містить жодного ребра.

Наприклад:


- не ланцюг

- це ланцюг, але не простий

- простий ланцюг

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

Граф називається зв’язаним, якщо будь-яка його пара вершин зв'язана.

Теорема 1.1 Будь-який неорієнтований граф розкладається єдиним чином в пряму суму своїх зв’язних компонент.

Доведення:

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

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

Теорема 1.2 В скінченому графі число вершин непарного ступеню парне.

Доведення:

Маємо вершин .

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

Наприклад:



Отже, в однорідному графі ступеня , який має вершин, кількість ребер 2.

  1   2   3   4

Схожі:

Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа icon+38(099)706 53 33 e-mail
Оригінальність його ще в тому, що він має 365 вікон (кількість днів у році), 52 кімнати (кількість тижнів у році) І 12 входів (місяців)…Замок...
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа iconПролог. "Хагакуре" І я. "Бал у графа д'Орже" Раймона Радіге та "Зібрання...
Тоді мені здавалося, що мені теж судилося піти на війну в молодому віці та загинути, тому я легко ототожнював себе з автором книги....
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа iconЛабораторна робота №40 визначення прискорення вільного падіння методом...
Мета роботи: ознайомитись з одним із методів визначення прискорення вільного падіння; визначити його значення за допомогою цього...
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа icon1. Науково-правничі школи в Україні
Законодавство не дає визначення поняття правнича школа, однак на локальному рівні є визначення поняття наукової школи вкну ім. Ш....
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа icon1. Визначення поняття “організація”. “
Визначення поняття “організація”.“Організація це група людей, діяльність яких свідомо координується для досягнення загальної мети...
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа iconВизначення поняття історико-географ регіон, охарактреризувати оснвні...
Дайте визначення предмету Історія України, вкажіть на основні методологічні принципи, джерела та значення його
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа iconЛекція 7 Тема Матеріальне стимулювання персоналу
«Не вписується» у ринкову економіку лише занижений, зрівняльний характер визначення її параметрів та централізований порядок затвердження...
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа icon7. Облік господарських процесів
Набуття навичок визначення фактичної собіваартості придбаних товарно-матеріальних цінностей, визначення фактичної собівртості виготовленої...
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа iconВизначення електричної ємності конденсатора за допомогою лічильного...
Мета роботи: вивчення поняття електричної ємності, методів її експериментального вимірювання, визначення електричної ємності конденсаторів...
Лекція №14. Визначення графа як абстрактного математичного поняття Визначення (p,q) графа, (1,0) графа iconЛекція №1 Тема. Основні поняття та визначення: зелений туризм, сільський...
...
Додайте кнопку на своєму сайті:
Школьные материалы


База даних захищена авторським правом © 2015
звернутися до адміністрації
skaz.com.ua
Головна сторінка