K-связность — различия между версиями
Строка 31: | Строка 31: | ||
Выберем вершину из правой компоненты.Тогда возможны варианты: | Выберем вершину из правой компоненты.Тогда возможны варианты: | ||
− | 1 | + | |
− | + | 1. Все <tex> l </tex> рёбер инцидентны вершине. Тогда: | |
− | + | ||
− | + | # Если вершина не единственна - удаляем вершину. | |
− | + | # Если вершина единственная, тогда: | |
− | 2 | + | ##Во второй компоненте <tex> l </tex> вершин - (??). |
+ | ## Удаляем её. | ||
+ | |||
+ | 2. Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы. | ||
}} | }} |
Версия 04:07, 27 октября 2011
Связность - одна из топологических характеристик графа.
Определение: |
Граф называется | - вершинно связным, если удаление любых вершин оставляет граф связным.
Вершинной связностью графа называется
вершинно - связен .
Полный граф
.
Определение: |
Граф называется | - реберно связным, если удаление любых ребер оставляет граф связным.
Реберной связностью графа называется реберно - связен
При
.Теорема: |
, где - минимальная степень вершин графа |
Доказательство: |
- очевидно. Рассмотрим граф . Покажем, что можем удалить l вершин и сделать граф несвязным.Выберем вершину из правой компоненты.Тогда возможны варианты: 1. Все рёбер инцидентны вершине. Тогда:
|
Определение: |
Множество компонентам графа | вершин, ребер или вершин и ребер разделяет и , если и принадлежат различным
Определение: |
Говорят, что вершины | и -разделимы, если минимальная мощность множества, разделяющего и равна
Многие утверждения для связных графов можно обобщить для случая -связности, однако аналог тривиального утверждения часто оказывается содержательным. Простейший пример - Теорема Менгера, утверждение которой для тривиально.