Знаймо

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

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

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

Двочастковий граф



План:


Введення

Біграф

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


1. Визначення

Повний двочастковий граф K 3,2

Неорієнтований граф G = (W, E) називається дводольним, якщо безліч його вершин можна розбити на дві частини U \ cup V = W , | U |> 0 , | V |> 0 , Так, що

  • жодна вершина в U не з'єднана з вершинами в U і
  • жодна вершина в V не з'єднана з вершинами в V

Двочастковий граф називається повним, якщо для кожної пари вершин u \ in U, v \ in V існує ребро (U, v) \ in E . Для

| U | = i, | V | = j

такий граф називається K i, j


2. Властивості

  • Граф є дводольним тоді і тільки тоді, коли він не містить циклу непарної довжини. Тому двочастковий граф не може містити кліку розміром більше 2.
  • Граф є дводольним тоді і тільки тоді, коли він 2-розфарбовуємо (тобто його хроматичної число дорівнює двом)
  • Граф розбивається на пари різнокольорових вершин тоді і тільки тоді, коли будь-які k елементів однієї з часток пов'язані принаймні з k елементами іншої ( Теорема Холла).
  • Двочастковий граф, у якого в кожній частині більше 2 вершин, є непланарним.

3. Перевірка дводольними

Перевірка дводольними за допомогою парності відстаней

Для того, щоб перевірити граф на предмет дводольних, достатньо в кожній компоненті зв'язності вибрати будь-яку вершину і позначати решта вершини під час обходу графа (наприклад, пошуком в ширину або в глибину) по черзі як парні і непарні (див. ілюстрацію). Якщо при цьому не виникне конфлікту, всі парні вершини утворюють безліч U , А всі непарні - V .


4. Застосування



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

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

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