страница1/78
Дата03.01.2019
Размер8.45 Mb.

Основные положения теории графов Определение графа


  1   2   3   4   5   6   7   8   9   ...   78

2. Основные положения теории графов
2.1 Определение графа
Рассмотрим множество V, состоящее из соединенных некоторым образом точек. Элементы - вершины графа. Граф G=G(V) с множеством вершин V есть некоторое семейство сочетаний или пар вида

указывающие, какие вершины считаются соединенными.



В соответствии с геометрическим представлением графа каждая конкретная пара называется ребром (дугой) графа, и - концевые точки.

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

Можно считать, что множество направленных дуг E, соединяющих элементы множества V, отображают это множество само в себя. Поэтому можно считать граф заданным, если дано множество его вершин V и способ отображения Г множества V в V (Г:VV). Таким образом, граф G есть пара (V, Г), состоящая из множества V и отображения Г, заданного на этом множестве.



G=(V, Г). 2.1

Так, рис. 2.1 изображен граф, вершинами которого являются точки a, b, c, d, e, g, h, а дугами – отрезки (a, a), (c, b), (c,d), (c, e), (d, c), (d, d), (e, d), (g, h). Отображение приведенного графа будет определяться следующим образом: Га={а}; Гb=; Гс={b, d, e}; Гd={d,c}; Ге={d}; Гg={h}; Гh=.




  1   2   3   4   5   6   7   8   9   ...   78

Коьрта
Контакты

    Главная страница


Основные положения теории графов Определение графа