Глава 1. ВВЕДЕНИЕ
1. Графы. Определение
Граф задается множеством точек или вершин (которое обозначается через X) и множеством линий или ребер (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф полностью задается (и обозначается) парой
Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (рис. Если ребра не имеют ориентации, то граф называется неориентированным (рис. 1.1(б)). В случае когда является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий будем обозначать как
В этой книге, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. обозначение относится к дуге а к дуге
Другое, употребляемое чаще описание ориентированного графа состоит в задании множества вершин X и соответствия которое показывает, как между собой связаны вершины. Соответствие называется отображением множества а граф в этом случае обозначается парой
Для графа на рис. 1.1(a) имеем т. е. вершины являются конечными вершинами дуг, у которых начальной вершиной является
Рис. 1.1. (см. скан) (а) Ориентированный граф. (б) Неориентированный граф. (в) Смешанный граф.
В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рис. предполагается, что соответствие задает такой эквивалентный ориентированный граф, который