Инструменты пользователя

Инструменты сайта


examination:diskretka:question12

Вопрос №12. Отношение связности (слабой и сильной) и достижимости для вершин графа. Базисный подграф

Здесь нету про слабую и сильную связность. И про достижимость надо бы пару слов. воооот

Отношения связности для вершин неорграфа

Пусть G - неорграф с V и E.
Мы говорим, что вершина V связана с вершиной W, если в графе G имеется маршрут с началом V и концом W.


Утверждение

Если существует маршрут, связывающий V и W, то найдется и простая цепь, связывающая V с W.

Доказательство

Идея доказательства заключается в срезании циклов:
Пусть существует маршрут из V в W, не являющийся цепью.
Стало быть, имеется некоторая вершина «U» маршрута, инцидентная более чем двум его ребрам.
Пусть e' - первое по порядку из ребер маршрута, инцидентное «U», e'' - последнее такое ребро:

в результате срезания с вершины U замкнутого маршрута из U в U:

это - простая цепь, ч.т.д.


Утверждение

Отношение связности является отношением эквивалентности на множестве вершин неорграфа.

Доказательство

Доказательство тривиально (т.к. существует транзитивность, симметричность, и […]← впишите что нужно, я хз)

Следствие

Относительно отношения связности вершины графа распадаются на компоненты связности

Замеачние

Рассмотрим какую-либо компоненту связности графа G (компоненту связности множества его вершин).
Добавим к вершинам, составляющим эту компоненту, все ребра графа G, инцидентные хотя бы одной вершине этой компоненты.
Легко проверить, что получается некоторый подграф графа G, который мы будем называть компонентой связности исходного графа G.

Определение

Граф называется связным, если состоит из единственной компоненты связности.

Замечание

Компонента связности графа исчерпывающим образом определяется матрицей связности этого графа.
В связи с этим будем использовать следующую формулу для матрицы связности:

В этой формуле сложение и умножение понимается булевым образом («+» = V; «*» = ^)


Базисный подграф (из вопроса №20)

Базисный граф: пусть имеется орграф Г; минимальная часть графа Г, индуцирующая на множестве вершин графа Г отношение достижимости графа Г, называется базисным графом графа Г.

Базисный граф графа Г определяется следующими условиями:

  1. Элемент нумерованного спискаесли в Г имеется путь, соединяющий 2 произвольно взятые его вершины, то и в базисном графе графа Г существует путь, содержащий эти вершины (в том же направлении)
  2. Элемент нумерованного спискаминимальность: любая собственная часть базисного графа графа Г базисным графом графа Г не является

Замечание 1: вообще говоря, орграф имеет более 1 базисного графа Замечание 2: если орграф Г конечен, то он всегда имеет хотя бы 1 базисный граф. Доказательство тривиально: следует последовательно уменьшить исходный граф, удаляя его дуги. После удаления очередной дуги надо проверить, индуцирует ли образовавшаяся часть графа Г на вершинах графа Г отношение достижимости. Если индуцирует, то процесс надо продолжить, если нет, то та часть графа Г, которая была получена в процессе осуществления алгоритма непосредственно перед данной частью и является базисным графом.

Замечание: теорема о существовании базисного графа в конечном орграфе может быть распространена на случай произвольного орграфа. Такое обобщение требует применения аксиомы выбора (точнее леммы Цорна).

examination/diskretka/question12.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)