Протоколы Internet


Элементы теории графов


10.21 Элементы теории графов

Семенов Ю.А. (ГНЦ ИТЭФ)

Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computer science). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т.д. Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки. На рис. 10.21.1А и 10.21.1Б приведены примеры обычного и ориентированного графа.

Рис. 10.21.1 Примеры неориентированного и ориентированного графов (А и Б)

Введем более строгие определения. Граф представляет собой структуру П = <V,E>, в которой V представляет собой конечный набор узлов, а EН VЕV представляет собой конечный набор ребер. Для ориентированного графа E Н Vґ V – конечный набор ориентированных ребер. Ребром может быть прямая или кривая линия. Ребра не могут иметь общих точек кроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку из множества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V. Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер. Параллельными ребрами графа называются такие, которые имеют общие узлы начала и конца.

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

Граф G называется плоским, если его можно отобразить в плоскости без пересечения его граней.

Очертанием графа (face) считается любая топологически связанная область, ограниченная ребрами графа.

Неориентированный граф G = <V,E> называется связанным, если для любых двух узлов x,y О V существует последовательность ребер из набора E, соединяющий x и y.




Начало  Назад  Вперед



Книжный магазин