Графы и их простейшие свойства.

ЧЕЛЯБИНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ.

Дискретная математика.

Лекции.

(для студентов физического факультета)

Чванова А.Н.

доцент кафедры математического анализа

Челябинск 2011г.

Теория графов

Историческая справка.

17 в. – начало использования графов в ходе решения головоломок.

1736 г. – появление теории графов (Эйлер опубликовал 1-ую статью о графах).

19в. – теория графов получила серьёзные применения в химии, биологии, электросхемах и т.д.

30-е гг., 20 в. –теория графов была впервые представлена как отдельная математическая дисциплина в работах венгерского математика Кёнига.

Современные области применения теории графов:

1. теория планирования и управления,

2. теория расписаний,

3. социология,

4. математическая лингвистика,

5. экономика,

6. биология,

7. медицина,

8. электроника,

9. программирование,

11. решение вероятностных и комбинаторных задач

и другие области.

Графы и их простейшие свойства.

Графом на плоскости или в пространстве называется конечное множество точек, некоторые из которых соединены линиями. Эти точки называются вершинами графа, а соединяющие их линии – рёбрами.

Примеры графов:

ü чёртёж многоугольника,

ü карта автомобильных дорог,

ü электросхема,

ü план предприятия,

ü блок-схема и др.

Вершина графа называется изолированной, если из неё не выходит ни одного ребра.

Если все вершины графа – изолированные, то он называется «нуль-граф».

Граф называется полным, если любые две его вершины соединены непосредственно ребром, причём желательно, чтобы при этом не было пересечений ребер.

Свойство полного графа:

Если у полного графа n вершин, то число его рёбер . Доказать применяя комбинаторный анализ (количество сочетаний из n элементов по 2).

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

Степенью вершины графа называется число рёбер, выходящих из этой вершины.

Степень вершины графа называется чётной (нечётной), если число рёбер, выходящих из этой вершины чётно (нечётно).

Теорема1: