Тема 1. Основные понятия теории графов.

1.1.Основные понятия теории графов.

1.2 Операции над графами.

1.3.Связность графов.

1.4.Эйлеровы графы.

1.5.Гамильтоновы графы.

1.1 Основные понятия теории графов.

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

Таким образом граф можно представить как совокупность двух множеств V-точек и U-линии, между элементами которых определено отношение инцидентности, т.е каждый элемент u  U инцидентен равно двум элементам v1,v2  V (или каждая вершина инцидентна какому-либо ребру) : G=<V,U>.