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

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

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


        a   b   c                 a
                                                  a              1
                              3        1

                              c        b              c      3
        1   2   3                                 2              b
                                  2


                        Один и тот же граф.

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

  Полустепенью исхода вершины x - -(x) называется число исходящих из нее дуг
-(x3) = 3.
  Полустепенью захода вершины x - +(x) называется число заходящих в нее дуг
+(x3) = 2.
   = -(x) + +(x). - степень вершины х.

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

Теорема: В графе без петель, где вершин больше двух всегда найдется пара вершин с
одинаковой степенью.
Доказательство заменим решением задачки «про шахматистов»:
   Пусть среди n человек нет двух таких, кто сыграл бы одинаковое число партий в
шахматном турнире. Тогда обязательно должно быть:
             1-ый сыграл: 0 партий
             2-ой сыграл: 1 партию

                                        — 48 —