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

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


examination:diskretka:question7

Вопрос №7. Простые графы. Представление простых графов бинарными отношениями. Полный простой граф. Дополнение простого графа

Простой граф - граф, не имеющий петель и кратных ребер.

Полный простой граф - граф, у которого каждая пара вершин соединена ребром (нет изолированных вершин).

Представление простых графов бинарными отношениями.

Любой граф G(V,E) с петлями, но без кратных дуг задает бинарное отношение E на множестве V и обратно.

Достижимость и частное упорядочение.

Если

  1. Нет циклов ⇒ нет петель ⇒ достижимость антирефлексивна
  2. Если существуют пути v→w и w→u ⇒ есть пути v→u ⇒ достижимость транзитивна
  3. Пусть достижимость — это не строгое упорядочение. Тогда существует u,v для которых u→v и v>u

то есть существует путь из u в v и из v в u. Следовательно, существует контур (u,v) + (v,u), что противоречит условию.

То из этого следует теорема: Если орграф G(V,E) не имеет контуров, то достижимость есть строгое частичное упорядочение.

Транзитивное замыкание

Если Е — бинарное отношение на V, то транзитивным замыканием Е+ на V будет отношение достижимости на орграфе G(V, E).

Теорема: Пусть М — матрица смежности орграфа G(V,E). Тогда Mk[i,j] = 1 в том и только в том случае, если существует путь длиной к из вершины vt в вершину Vj.

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