1. Основные понятия теории графов

Теория графов может рассматриваться как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество X, состоящее из n

элементов (X = {1, 2, ..., n}), называемых вершинами графа, и подмножество V декартова произведения X XX, то есть V сX2, называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V) (неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X). Дугу между вершинами i и j, i, j е X, будем обозначать (i, j). Число дуг графа будем обозначать m (V = (v1, v2, ..., vm)).

Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.