Графы

[mr.tumkan]

1) В турнирном графе, содержащем $n\geqslant 3$ вершин, есть простой цикл. Докажите, что в этом графе есть цикл из трёх вершин. (Разумеется, ребра цикла должны быть ориентированны так, чтобы его можно было обойти не нарушая правил движения.)

Пронумеруем вершины $1;2;3;...;n$

Я так полагаю, что можно сотворить такой граф $(3,1);(1,2);(2,3);(3;4);(4;5);...;(n-1,n)$

Как раз цикл и есть $(3,1);(1,2);(2,3);$

Или так не годится?

2) В ориентированном графе нет (ориентированных) циклов. Докажите, что его вершины можно пронумеровать так, чтобы все рёбра были направлены от вершины с меньшим номером к вершине с большим номером.

Не очень ясен вопрос. А почему бы и не пронумеровать ,что потенцально может помешать, коли нет циклов? Что тут будет считаться доказательством?

[patzer2097]

mr.tumkan в сообщении #921659 писал(а):

1) В турнирном графе, содержащем $n\geqslant 3$ вершин, есть простой цикл. Докажите, что в этом графе есть цикл из трёх вершин. <...> Или так не годится?

Не годится, надо хотя бы вот так: "Если бы тройных циклов не было, то отношение 'существует ребро, идущее из x в y' было бы линейным порядком на множестве вершин, что противоречит условию".

mr.tumkan в сообщении #921659 писал(а):

2) В ориентированном графе нет (ориентированных) циклов. Докажите, что его вершины можно пронумеровать так, чтобы все рёбра были направлены от вершины с меньшим номером к вершине с большим номером.

Не очень ясен вопрос. А почему бы и не пронумеровать ,что потенцально может помешать, коли нет циклов? Что тут будет считаться доказательством?

Если Вы о конечных графах говорите, то и это утверждение тривиально, - ведь в конечном ориентированном графе без циклов найдется вершина, из которой не выходит ни одно ребро.

[mr.tumkan]

patzer2097 в сообщении #922362 писал(а):

mr.tumkan в сообщении #921659 писал(а):

1) В турнирном графе, содержащем $n\geqslant 3$ вершин, есть простой цикл. Докажите, что в этом графе есть цикл из трёх вершин. <...> Или так не годится?

Не годится, надо хотя бы вот так: "Если бы тройных циклов не было, то отношение 'существует ребро, идущее из x в y' было бы линейным порядком на множестве вершин, что противоречит условию".

А без линейных порядков тут не обойтись? Возможно ли как-то попроще?

-- 05.11.2014, 19:58 --

patzer2097 в сообщении #922362 писал(а):

mr.tumkan в сообщении #921659 писал(а):

Если Вы о конечных графах говорите, то и это утверждение тривиально, - ведь в конечном ориентированном графе без циклов найдется вершина, из которой не выходит ни одно ребро.

А почему найдется такая вершина?

[arseniiv]

Иначе вперёд и вперёд без устали — какая уж тут конечность!