UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваОрієнтовані графи (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2086
Скачало227
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

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

 

Крім моделі, яка була розглянута у попередніх розділах, у теорії

досліджуються й інші типи графів. Наприклад,

 

мультиграф ( граф, в якому припускаються кратні ребра, тобто будь-які

дві вершини можна з’єднати декількома ребрами. Псевдограф ( мультиграф,

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

Гіперграф ( граф, в якому ребрами можуть бути не лише двоелементні, але

довільні підмножини множини вершин. Нарешті, важливою для різноманітних

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

орграфом. У цьому розділі дамо короткий огляд основних понять і

результатів для орграфів.

 

Орієнтованим графом, або орграфом, G називається пара множин (V,E ), де

Е (V ?V. Елементи множини V називаються вершинами орграфа G, а елементи

множини Е ( дугами орграфа G  =(V,E ). Отже, дуга ( це впорядкована пара

вершин. Відповідно, V називається множиною вершин і Е ( множиною дуг

орграфа G.

 

Якщо е= (v,w) ( дуга, то вершина v називається початком, а вершина w (

кінцем дуги е. Кажуть, що дуга е веде з вершини v у вершину w або

виходить з v і заходить у w. Дугу е і вершини v та w називають

інцидентними між собою, а вершини v i w суміжними.

 

Дуга (v,v), в якій початок і кінець збігаються називається петлею.

Надалі розглядатимемо тільки орграфи без петель.

 

Як і звичайний граф, орграф G =(V,E ) може бути заданий шляхом переліку

елементів скінченних множин V i E, діаграмою або за допомогою матриць.

 

Діаграма орграфа відрізняється від діаграми звичайного графа тим, що

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

що йдуть від початку до кінця дуги. Напрямок лінії позначається

стрілкою.

 

Занумеруємо всі вершини орграфа G =(V,E ) натуральними числами від 1 до

n; дістанемо множину вершин V у вигляді {v1,v2,...,vn}. Матрицею

суміжності А орграфа G називається квадратна матриця порядку n, в якій

елемент і-го рядка і j-го стовпчика

 

1, якщо (vi,vj)(E ;

 

aij =

 

0, у противному разі.

 

Занумеруємо всі вершини орграфа G =(V,E ) числами від 1 до n, а дуги (

числами від 1 до m. Матрицею інцидентності В орграфа G називається

n?m-матриця, в якій елемент і-го рядка і j-го стовпчика

 

1, якщо вершина vi є початком дуги ej ;

 

bij = (1, якщо вершина vi є кінцем дуги ej ;

 

1, якщо вершина vi і дуга ej неінцидентні.

 

Орграфи G1=(V1,E1) i G2=(V2,E2) називаються ізоморфними, якщо існує таке

взаємно однозначне відображеня ? множини V1 на множину V2, що дуга

(v,w)?Е1 тоді і тільки тоді, коли дуга (?  (v),?  (w))?Е2.

 

Очевидно, що теорема 3.1 справедлива і для орграфів.

 

Півстепенем виходу вершини v (позначається ?+(v)) орграфа G називається

кількість дуг орграфа G, початком яких є вершина v. Півстепенем заходу

вершини v (позначається ?—(v)) орграфа G називається кількість дуг

орграфа G, кінцем яких є вершина v.

 

Аналогічно теоремі 3.3 може бути доведено таку теорему.

 

?—(v)= |E |.

 

Значна частина властивостей та тверджень стосовно звичайних графів може

бути без змін сформульована і для орграфів. Зокрема, це стосується цілих

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ