20508

Неорієнтовані та орієнтовані графи

Доклад

Информатика, кибернетика и программирование

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

Украинкский

2013-07-25

27 KB

25 чел.

Неорієнтовані та орієнтовані графи.

Граф — це сукупність об'єктів із зв'язками між ними.

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

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

Неорієнтований граф

Граф або неорієнтований граф  — це впорядкована пара , для якої виконуються наступні умови:

— множина вершин або вузлів,

— множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин, які називають ребрами.

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

Орієнтований граф

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

64818. ТЕХНОЛОГІЯ ВІДНОВЛЕННЯ КАНАЛІЗАЦІЙНИХ КОЛЕКТОРІВ З ВИКОРИСТАННЯМ КОНСТРУКЦІЙ ІЗ ШЛАКОВОГО ЛИТТЯ 3.18 MB
  Значна частина каналізаційних мереж України перебуває у передаварійному та аварійному стані і потребує термінового відновлювання. Через корозію абразивний знос розгерметизацію стикових з’єднань конструкції каналізаційних мереж передчасно руйнуються втрачаючи несучу здатність...
64819. ПАРАМЕТРИ ЗМІН ФІЗИКО-ХІМІЧНИХ ВЛАСТИВОСТЕЙ СІРОГО ЛІСОВОГО ҐРУНТУ ПІД ВПЛИВОМ УДОБРЕННЯ КУЛЬТУР І ПІСЛЯДІЇ ВАПНУВАННЯ 237 KB
  Метою досліджень було встановити закономірності впливу післядії вапнування з використанням різних систем удобрення на родючість сірого лісового ґрунту а саме: фізикохімічні властивості процеси перетворення кальцію вмісту гумусу агрохімічні...
64820. Фізичні поля прийомних криволінійних акустичних антен з екранами 9.9 MB
  Криволінійні антенні решітки що утворені з кругових циліндричних п’єзокерамічних перетворювачів відносять до антен що знайшли найбільш широке застосування як у підводній електроакустичній апаратурі та пристроях так і в іншому обладнанні акустичної техніки.
64821. ФУНКЦІЯ НАДАННЯ ПОСЛУГ НАСЕЛЕННЮ ОРГАНАМИ ВНУТРІШНІХ СПРАВ УКРАЇНИ: ТЕОРЕТИКО-ПРАВОВИЙ АСПЕКТ 179 KB
  Вагоме місце в цьому переліку займає впровадження у повсякденну поліцейську практику функції надання послуг населенню. Мюнстер ФРН підкреслювалося що поліція має перетворитися на сервісну службу розвивати систему послуг для громадян.
64822. Обґрунтування резервів підвищення тягових якостей локомотива та їх реалізація керуванням ковзання в системі колеса з рейкою 276.5 KB
  Проблема реалізації максимальних тягових зусиль – складне та багатофакторне завдання, яке пов’язане зі значним різноманіттям конструктивних та експлуатаційних параметрів локомотива. Неточність статичного та динамічного розважування, різниця тягових зусиль та умов зчеплення...
64823. РАДІОВИМІРЮВАЛЬНІ ПРИЛАДИ НА ОСНОВІ ЄМНІСНОГО ЕФЕКТУ В ТРАНЗИСТОРНИХ СТРУКТУРАХ З ВІД’ЄМНИМ ОПОРОМ 425.5 KB
  Сучасний стан розвитку радіовимірювальної техніки суттєвим чином залежить від новітніх досягнень в області розробки методів та засобів радіовимірювань та визначається використанням вдосконалених або принципово нових приладів.
64824. Міжнародна економічна діяльність країн в умовах глобалізації ринку чорних металів 194 KB
  Актуальність наукової розробки обраної теми обумовлена як впливом глобальних процесів розвитку торгових відносин та кон’юнктурних коливань на світовому ринку чорних металів на міжнародну економічну діяльність країн так і посилена...
64825. ЛІКУВАННЯ, ПРОФІЛАКТИКА ТА ПРОГНОЗУВАННЯ МНОЖИННОГО КАРІ3ЄСУ ЗУБІВ У ПІДЛІТКІВ 230 KB
  Проблема розвитку множинного каріозного процесу у підлітків з точки зору психологічних особливостей, що обумовлюють вегетативні порушення, на даний момент недостатньо висвітлена. Застосування комплексного підходу до їх вивчення дасть можливість...
64826. МЕТОД СИНТЕЗУ ДИСКРЕТНИХ СИГНАЛІВ ДЛЯ ПІДВИЩЕННЯ АБОНЕНТСЬКОЇ ЄМНОСТІ СИСТЕМ РАДІОЗВ’ЯЗКУ З КОДОВИМ РОЗДІЛЕННЯМ КАНАЛІВ 899.5 KB
  Становлення та розвиток телекомунікаційних систем України як незалежної держави проходить у відповідності з Концепцією розвитку зв’язку в Україні, яка визначає основні підходи до розвитку та особливостей структурної перебудови зв’язку.