- ЗАДАЧИ ТЕОРИИ ГРАФОВ
Геометрический граф в пространстве n (Эвклидово пространство) – это множество V={vi} точек пространства n и множество Е={ek} простых кривых удовлетворяющих следующим условиям.
1)Каждая замкнутая прямая из множества Е содержит только одну точку v множества V;
2)Каждая незамкнутая прямая из множества Е содержит только 2 точки v из множества V, которые являются ее границами.
3)Кривые Е не имеют общих точек за исключением точек из множества V
Граф – это совокупность не пустого множества V, изолированного от него множества Е и отображения : ЕVV.
Если граф не имеет ребер, он называется вырожденным. Если множества Е и V конечные, то граф называется конечным.
1.1 Формализованное задание графа
Граф задается на множестве вершин V и множестве ребер Е. Наиболее простое описание графа – составление таблицы соответствия ребер и вершин.
Для удобства описания графа часто используют матрицы инциденций, смежности, циклов, разрезов и путей.
1.1.1 Описание графа с помощью таблицы