Газовые сети состоят из участков, по которым движется газ, и узлов, в которых соединяются участки и к которым присоединяют ответвления к потребителям. Геометрические фигуры, состоящие из ребер и вершин, когда каждому ребру соответствуют две вершины, являющиеся концами этих ребер, называют графами. У связного графа каждая вершина может быть соединена цепью ребер с любой другой вершиной. Любая газовая сеть представляет собой конечный связный ориентированный граф, состоящий из конечного числа вершин (узлов), соединенных между собой ребрами (участками). Примеры газовых сетей, представляющих собой конечные связные ориентированные графы. Графы, у которых ребра пересекаются только в узлах, называются плоскими. Большинство газовых сетей можно представить в виде плоских графов. Цепочка последовательно соединенных ребер (участков), в которой каждую вершину (узел) при движении по направлению потока проходят один раз, называется путем.
Деревом графа называется подграф, содержащий все вершины графа и не имеющий ни одного замкнутого контура. Ребра, входящие в дерево, называются его ветвями. Тупиковая разветвленная газовая сеть представляет собой дерево (а', б'). Кольцевая сеть представляет собой граф, состоящий только из циклов и не имеющий тупиковых ответвлений (а, б). Большинство газовых сетей представляют собой смешанный граф, состоящий из замкнутых контуров и тупиковых ответвлений. Граф (кольцевую сеть) можно трансформировать в дерево путем исключения из каждого цикла замыкающего участка. Очевидно, число замыкающих участков равно числу элементарных циклов. Так, из кольцевых сетей а, б получаются деревья а', б' путем исключения замыкающих участков, показанных на рисунке пунктиром. В качестве замыкающих можно принимать различные участки сети, поэтому из каждой кольцевой сети можно получить несколько деревьев.
