Операції над множинами | Правила рішення рівнянь і систем рівнянь з одним невідомим в алгебрі множин. | Завдання до виконання роботи | Основні відомості про графах | Способи завдання графів | Можливості підключення в графах | розфарбування графа | Фундаментальні цикли графа | Завдання до виконання роботи | Диз'юнктивна і Кон'юнктивна нормальні форми |

загрузка...
загрузка...
На головну

Стійкі безлічі вершин графа

  1. II. 11. Наведіть принципову схему установки і поясніть, як в лабораторній роботі визначали чутливість осцилографа.
  2. II. 9. Поясніть принцип дії електронного осцилографа.
  3. Автори: проф., Д.е.н. В. В. Вершинін
  4. Вершин теодолітного ходу
  5. Вершин теодолітного ходу
  6. ВЕРШИНА БЛАЖЕНСТВА
  7. Вершина відродження (1980-1984)

Безліч вершин графа називається внутрішньо стійким (Незалежним), якщо ніякі дві вершини з цього безлічі не суміжні.

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

Найбільше за потужністю стійке безліч називається найбільшим.

Найбільше внутрішньо стійке безліч є максимальним, зворотне невірно.

Поняття внутрішньої стійкості на змістовному рівні зводиться до пошуку рішення задачі, наприклад, про восьми ферзів: потрібно так розставити на шахівниці найбільше число ферзів, щоб вони не били один одного. Таких ферзів не може бути більше восьми, тому що ніякі два з них не повинні перебувати на одній вертикалі, горизонталі або діагоналі.

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

Число вершин в найбільшому внутрішньо стійкому безлічі графа G називається числом внутрішньої стійкості і позначається a0 (G)


рис.1

На рис.1 зображено граф G, у якого найбільшими внутрішньо стійкими є безлічі вершин {1,2,3,7}, {1,2,3,8}, {2,3,5,7}, {4,7 }, {2,3,5,8}; отже, aO (G) = 4. Безліч {4,7} є максимальним внутрішньо стійким, але не найбільшим.

Підмножина V 'вершин графа G називається зовні стійким, Якщо кожна вершина, яка не належить цій безлічі (V \ V '), суміжно з деякою вершиною з V'.

Зовні стійке безліч називається мінімальним, Якщо ніяке його власне підмножина не є зовні стійким.

Зовні стійке безліч називається найменшим, Якщо його потужність найменша.

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

Число вершин в мінімальному зовні стійкому безлічі меншої потужності називається числом зовнішньої стійкості і позначається bo (G)

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

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

У прикладі на рис.1 безлічі Х1 = {4,5,6,8}, Х2 = {4,5,6,7}, ХЗ = {1,2,3,5,6,8} є покриттям, причому, Х1 і Х2 - найменші покриття, а ХЗ - мінімальне. Безліч вершин графа, що є одночасно і внутрішньо і зовні стійким, називається ядром графа.



Завдання до виконання роботи | Визначення чисел стійкості графа
загрузка...
© um.co.ua - учбові матеріали та реферати