Студопедия
Контакти
 


Тлумачний словник

Реклама: Настойка восковой моли




Авто | Автоматизація | Архітектура | Астрономія | Аудит | Біологія | Будівництво | Бухгалтерія | Винахідництво | Виробництво | Військова справа | Генетика | Географія | Геологія | Господарство | Держава | Дім | Екологія | Економетрика | Економіка | Електроніка | Журналістика та ЗМІ | Зв'язок | Іноземні мови | Інформатика | Історія | Комп'ютери | Креслення | Кулінарія | Культура | Лексикологія | Література | Логіка | Маркетинг | Математика | Машинобудування | Медицина | Менеджмент | Метали і Зварювання | Механіка | Мистецтво | Музика | Населення | Освіта | Охорона безпеки життя | Охорона Праці | Педагогіка | Політика | Право | Програмування | Промисловість | Психологія | Радіо | Регилия | Соціологія | Спорт | Стандартизація | Технології | Торгівля | Туризм | Фізика | Фізіологія | Філософія | Фінанси | Хімія | Юриспунденкция

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

Загрузка...

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

Граф позначається буквою G, множина вершин V, множина відношень (дуг або ребер) – E, упорядкована пара G = (V, E). Нехай V = {v1, v2, ..., vn} і E = = {e1, e2...,em}

При цьому елементи множини V зобра­жають крапками на площині, а ребра (vi, vj ) — відрізками (прямоліній­ними або криволінійними), які з'єднують крапки vi та vj. Граф називаєть­ся скінченним, якщо множини його вершин і ребер є скінченними. Кількість вершин графа n, а кількість ребер m. Граф, який містить n вершин та m ребер називають (n, m) - графом.

Кількість вершин n(G) графа називають його порядком.

Рис. 2.

 

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

Граф G = (V, E), V = {v1, v2, v3 v4,, v5} і E = {e1, e2, e3, e4, e5, e6}. Ребра можуть задаватися ще послідовністю вершин E = {(v1, v5), (v1, v5), (v1, v3), (v2,,v3),(v2,v4), (v2, v5), (v4, v5)}.

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

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

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

 

Рис. 3.

 

Таким чином для простого графа – граф складається з двох множин (вершин та ребер), для несиметричного графа – граф складається з двох множин (вершин та дуг).

Два ребра називаються суміжними, якщо обидва вони є інцидентними одній вершині.

 

Рис. 4.

 

Якщо граф G = (V, Æ ) - множина відношень порожня (рис. 4, а).

Але якщо множина вершин V - порожня, то порожньою є також множина Е. Такий граф називається порожнім. Такий граф нази­вається нуль-графом і позначається Æ (рис. 4, b).



Интернет реклама УБС

Лінії, що зображають ребра графа, можуть перетинатися, але точки перети­ну не є вершинами; різні ребра можуть бути інцидентними одній і тій самій парі вершин (рис.2), такі ребра називаються кратними. Цей випадок відповідає наявності кількох однакових пар E = {(v1, v5), (v1, v5). Граф, що містить кратні ребра, називається мультиграфом.

Ребро може з'єднува­ти деяку вершину саму з собою (рис. 5), таке ребро називається петлею. Цей випадок відповідає наявності в множині Е пар вигляду (v, v). Граф із петлями та кратними ребрами називається псевдографом.

Рис. 5

 

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

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

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

Рис. 6.

 

Повний граф G = (V, E), n =_, m = _ .

Кожне ребро ek Î E з’єднує пару вершин vi, vj Î V, які є його кінцями ці вершини граничні. Розрізняють початкову вершину з якої дуга виходить та кінцеву вершину , в яку дуга входить. Дві вершини (граничні вершини) які з’єднані двома або більше ребрами називаються кратними.

В загальному випадку граф може містити і ізольовані вершини які не є граничними вершинами ні з одним з ребер.

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

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

Інцидентність. Задання графа за допомогою матриці інцидентності.

 

Задати граф означає задати множини його вершин і ребер, а також відношення інцидентності. Коли граф G — скінченний, тоді вершини даного графа v1 ,v2,,..., vn, а його ребра е1, е2,..., еm. Відношення інцидентності можна оз­начити матрицею S= _, що має n рядків й т стовпців. Рядки відпо­відають вершинам графа, а стовпці відпо­відають його ребрам. Якщо вершина vi є інцидентною ребру ео, , то sij = 1, в іншому випадку sij = 0. Це матриця інци­дентності звичайного графа G, яка є одним із способів його визначення (для графа на рис. 2).

Sij = _

 

_

;

 

У матриці інцидентності _ орієнтованого графа G, якщо вершина vi —початок ребра ej, то sij = 1; якщо vi: - кінець ej, то sij = -1. Кількість одиниць у рідку дорівнює степені відповідній вершині (для орграфа кількість позитивних одиниць визначає позитивну степінь, а кількість від’ємних одиниць - від’ємну степінь). Нульовий рядок відповідає ізольованій вершині, а нульовий стовпець - петлі.

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

Sij = _

 

Sij = _.

 

 



Читайте також:

  1. II. Основні закономірності ходу і розгалуження судин великого і малого кіл кровообігу
  2. II. Поняття соціального процесу.
  3. V. Поняття та ознаки (характеристики) злочинності
  4. А .Маршалл - основоположник неокласичної теорії.
  5. А/. Поняття про судовий процес.
  6. Адвокатура в Україні: основні завдання і функції
  7. Адміністративний проступок: поняття, ознаки, види.
  8. Адміністративні провадження: поняття, класифікація, стадії
  9. Аксіоматичний метод у математиці та суть аксіоматичної побудови теорії.
  10. Акти застосування юридичних норм: поняття, ознаки, види.
  11. Альтернативні теорії вартості
  12. Альтернативні теорії капіталу

Загрузка...



<== попередня сторінка | наступна сторінка ==>
Однорідні системи лінійних алгебраїчних рівнянь. | Властивості матриці інцидентності

Не знайшли потрібну інформацію? Скористайтесь пошуком google:


 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.005 сек.