Теория графов. Ориентированные графы

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

    Задача4. Доказать, что в транзитивном турнире существует ровно один гамильтонов путь.

    Доказательство: Ранее доказывалось, что в любом турнире существует гамильтонов путь. Допустим, что в транзитивном турнире G c n вершинами существует не один такой путь. Возьмем первый гамильтонов путь, и, не ограничивая общности, пронумеруем вершины в порядке обхода. Получим путь , который содержит все n вершин данного турнира. По определению транзитивности орграфа справедливо, что если существуют дуги и , то также существует дуга , а отсюда, аналогично следует существование дуги . В итоге в транзитивном турнире множество дуг AG определяется весьма однозначно. Имеем множество дуг , а также ребро . Рассмотрим теперь другой путь, начинающийся с некоторой вершины . Допустим, следующей вершиной данного пути является вершина или . Второй случай невозможен, поскольку в транзитивном турнире нет дуг из вершин с высшим номером в вершину с более низким. Отсюда также следует, что если мы из вершины перешли в вершину , то в вершину вернуться невозможно. Согласно этому утверждению, все вершины во втором гамильтоновом пути(а в нашем случае даже в гамильтоновом контуре) будут обходиться в обозначенном первым путем порядке. Это означает что второй путь совпадает с первым, а значит, что в таком турнире существует ровно один гамильтонов путь.

    Задача5. Докажите, что неориентированный граф G является основанием некоторого сильного орграфа тогда и только тогда, когда G связный и не имеет мостов.

    Доказательство: Достаточное. Докажем, что если граф G связен и не имеет мостов, то он является основанием некоторого сильного орграфа. Действительно, если граф связен и не имеет мостов, то он не имеет висячих вершин и висячих компонент. Следовательно, степень каждой вершины равна двум и более. Выберем  в данном графе G цикл максимальной длинны и включающий в себя максимальное количество вершин.  Рассмотрим полученный подграф F. 

    Ориентируем в нем все ребра в одном  направлении так, чтобы любая  вершина цикла достигалась из любой. Теперь рассмотрим все остальные  вершины графа. Либо отдельная вершина, либо компонента, состоящая из нескольких вершин имеет минимум 2 ребра с вершинами выбранного нами подграфа F, в противном случае мы имеем мост, что противоречит изначальным условиям. Ориентируем данные ребра так, как и ребра в подграфе F. Тогда любая вершина из компоненты или любая отдельная вершина станет достижима из любой вершины F, ровно как и обратно, что соответствует определению сильного орграфа.

    Необходимое. Пусть дан сильный орграф. Доказать что его основание – связный  граф без мостов. Действительно, если граф G несвязен, то из изолированной вершины или компоненты нельзя попасть ни в какую вершину из другой компоненты, что говорит о том, что орграф не является сильным. Если мы имеем в графе G мост, связывающий компоненты и то, ориентировав это ребро (не важно из в или наоборот) мы сможем попасть, допустим, из любой вершины в любую из ,но из любой вершины в таком случае мы не сможем попасть ни в какую вершину . Следовательно, такой орграф не будет сильным. Значит сильный орграф может быть построен лишь из связного графа без мостов, взятого за основание.

    Задача6. Докажите, что пара векторов  (З², 2)  и (3, 2², 1)  является графической, и постройте ее реализацию.

    Решение:

    Первый  вектор представим в виде:

    (З², 2)=(3,3,2)

    Второй  в виде:

    (3,2,2,1)

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

d=(3,3,2), c=(3,2,2,1)

    Действительно:

3+3+2=3+2+2+1

    Первое  утверждение верно. Докажем второе.

(3+3-1,3+3-1,2+3-1,3,2,2,1)

(5,5,4,3,2,2,1)

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

    В итоге убеждаемся, что данная последовательность графическая, а следовательно, и пара данных векторов тоже является графической.

    Задача 7.Верно ли, что в орграфе порядка п, для любых двух несмежных вершин и и v которого верно неравенство d(u)+ d(v)>=2п — 3, существует гамильтонов путь.

    Приведём  пример: 

    n=4.  2n-3=5

    d(u)+d(v)>=5

    Для всех несовпадающих несмежных вершин u и v выполняется равенство d(u)+d(v)>=2n+3, однако гамильтонова пути не существует.

    Ответ: нет, не верно.

    Задача8. Транзитивным замыканием орграфа G называется орграф G’, для которого , тогда и только тогда, когда в орграфе G вершина v достижима из и. Транзитивная редукция орграфа G определяется как орграф с наименьшим числом дуг, транзитивное замыкание которого совпадает с транзитивным замыканием орграфа G. Покажите, что если орграф не имеет контуров, то его транзитивная редукция единственна.

    Построим  в графе G транзитивную редукцию, построим возможные пути максимальной длинны (d(u,v)>=2).

    Если  для пути (u,v)=(u, … w, … t, … v) существует ребро уменьшающее длину пути, то есть ,то это ребро выбираем из графа G. Выбрав все такие рёбра получим транзитивную редукцию графа G.

    Так как проводимые операции дают однозначную  выборку рёбер, то данная редукция является единственной.

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1.  Емеличев, В.А. Лекции по теории графов / В.А. Емеличев [и др.] – М. : Наука, 1990. – 384 с.
2. Зыков, А.А. Основы теории графов / А.А. Зыков. – М. , 1987. 381c.
3. Харари, Т. Теория графов / В.А. Харари. – М. , 1973. 300c
4. Оре, О. Теория графов / О. Оре. – М. , 1980. 336c.