Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Зв'язний граф



План:


Введення

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


1. Приклади застосування

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

2. Зв'язність для орієнтованих графів

В орієнтованих графах розрізняють кілька понять зв'язності.

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

Орієнтований граф називається слабо-зв'язковим, якщо є зв'язковим неорієнтований граф, отриманий з нього заміною орієнтованих ребер неорієнтованим.


3. Деякі критерії зв'язності

Тут наведені деякі критеріальні (еквівалентні) визначення зв'язного графа:
Граф називається однозв'язна (зв'язковим), якщо:

  1. У нього одна компонента зв'язності
  2. Існує шлях з будь-якої вершини в будь-яку іншу вершину
  3. Існує шлях із заданої вершини в будь-яку іншу вершину
  4. Містить зв'язний подграф, що включає всі вершини вихідного графа
  5. Містить як подграфа дерево, що включає всі вершини вихідного графа (таке дерево називається Остовним)
  6. При довільному розподілі його вершин на 2 групи завжди існує хоча б 1 ребро, що з'єднує пару вершин з різних груп

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Зв'язний список
Зв'язний простір
Локально зв'язний простір
Лінійно зв'язний простір
Граф
Граф Ессекс
Граф, Девід
Граф, Штеффі
Граф Дербі
© Усі права захищені
написати до нас
Рейтинг@Mail.ru