Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Ейлерови графи

Реферат Ейлерови графи





ми і q ребрами називається (p; q) - графом. Граф (1,0) - називається тривіальним. [6]

Якщо елементом множини V може бути пара однакових елементів u , то такий елемент множини V називається петлею. [3]

Типи графів:

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

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

В 



Рис.1 Рис.2


В· Орієнтований граф, або орграф, складається з кінцевого непорожньої множини V вершин і заданого набору Х упорядкованих пар різних вершин. Елементи з Х називаються орієнтованими ребрами, або дугами. Немає петель і кратних дуг (рис. 3). br/>

В В В В В  В В  Рис.3 В 

Рис.4

br/>




В· Спрямований граф - це орграф, що не має симетричних пар орієнтованих ребер (рис. 4).

В· Помічені графи (або перенумеровані), якщо його вершини відрізняються одна від іншої будь-якими позначками. В якості позначок зазвичай використовуються букви або цілі числа. [6]

Ступенем вершини v i у графі G називається число ребер, інцідентних v i , позначається d i . [6] Для орграфа вводяться поняття ступеня входу і виходу. Ступенем виходу вершини v називається кількість ребер, для яких v є початковою вершиною, позначається outdeg ( v ). Ступенем входу вершини v називається кількість ребер, для яких v є кінцевою вершиною, позначається indeg ( v ). Якщо indeg ( v ) = 0, то вершина v називається джерелом. Якщо outdeg ( v ) = 0, то вершина v називається стоком. [1]

В  Маршрути і зв'язність

Граф G / (U /, V /) називається подграфом графа G (U, V), якщо U / ГЊU і V / ГЊV. Позначення: G / ГЊG. p> Якщо V / = V, то G / називається остовне подграфом G. [3]

Маршрутом у графі G називається чергується послідовність вершин і ребер ця послідовність починається і закінчується вершиною, і кожне ребро послідовності інцидентне двом вершинам, одна з яких безпосередньо передує йому, а інша безпосередньо слід за ним. Зазначений маршрут з'єднує вершини v 0 і v n і його можна позначити v 0 v 1 v 2 ... v n (наявність ребер мається на увазі). Ця послідовність іноді називається ( v 0 - v n


Назад | сторінка 2 з 10 | Наступна сторінка





Схожі реферати:

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