Граф, вершина, ребро

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

Единого общепринятого определения графа нет. В зависимости от решаемой задачи принимается то или иное определение, которые похожи, но это не одно и то же.

1736 год. Эйлер доказывает, что задача о Кёнигсбергских мостах не имеет решения. Центральная часть Калининграда – это два берега реки Перголя и два острова этой реки. Острова соединены между собой мостом и у одного острова 2+2 моста с берегами и у другого 1+1. Всего 7 мостов. Задача: обойти все четыре части суши – два берега и два острова, пройдя по каждому мосту по одному разу.

1930 год. Казимир Куратовский доказывает, что задача о трех домах и колодцах не имеет решения. Имеется три дома и три колодца. Нужно проложить тропика от каждого дома к каждому колодцу так, чтобы они не пересекались.

1976 год. Аппель и Хейкен с помощью компьютера, перебрав около 2000 контр-вариантов показали, что достаточно 4-ёх красок для раскраски карты. Карта – это разбивка поверхности не пересекающимися областями.

Граф, вершина, ребро

Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что

.

Ориентированным графом (орграфом) будем называть такую произвольную пару G = <V, E>, что . В обоих случаях множества V и Е будем называть соответственно множеством вершин и множеством ребер графа G. Элементы множества Е для орграфа называются дугами

Граф G задается множеством точек или вершин х₁, х₂,..., х_n, которое обозначается через X, и множеством линий или ребер a₁, a₂,..., a_n, которое обозначается символом A, соединяющих между собой все или часть этих точек. Таким образом,граф G полностью задается (и обозначается) парой (X, А).

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

Линия, изображающая ребро {и, v}, или <и, v> ( угловые скобки используются для обозначения дуг орграфа. ), соединяет точки, изображающие вершины и, v причем во втором случае стрелка обозначает направление от и к v (рис. 1.1).

Рис. 1.1. а) Неориентированный граф; б) Ориентированный граф.

Дата добавления: 2015-07-07