Специальная математика. Соловьев А.Е. - 49 стр.

              :
              n-ый сыграл n-1 партий
              т.е. из вершины n-го игрока исходит (n-1) стрелка, а в 0-ую не входит ни одна.
Но этого не может быть.

Граф GA = <ГA, A> - называется подграфом графа G = <Г, X>, если A  Х, ГA  Г.


  Для неориентированных графов вместо дуги говорят ребро, вместо пути - цепь, вместо
контура - цикл.
    Граф называется связным (компонентом связности), если между любыми двумя
вершинами есть цепь.
                                 4.2. Теорема Эйлера

 Цепь называется эйлеровой, если она является простой и проходит по всем ребрам графа.
 Эйлеровым циклом называется простой цикл, проходящий по всем ребрам.
 Граф, имеющий эйлеровый цикл, называется эйлеровым графом.

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




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

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




Таким образом доказана необходимость того, чтобы все вершины были четными.

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

                                          — 49 —