Понятие графа. Способы представления графа
Граф – пара G = (V,E), где V – множество объектов произвольной природы, называемых вершинами, а E – семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство E могут содержать бесконечное число эле-ментов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и E конечны. Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным, сокращенно – орграф, иначе – неориентированным. Ребра орграфа называются дугами.
Если e = <u,v>, то вершины v и и называются концами ребра. При этом говорят, что ребро e является смежным (инцидентным) каждой из вершин v и и. Вершины v и и также называются смежными (инцидентными). В общем случае допускаются ребра вида e = <v, v>; такие ребра называются петлями.
Степень вершины графа – это число ребер, инцидентных данной вершине, причем петли учитываются дважды.
Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.).
Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг – в орграфе) вида v0, (v0,v1), v1, …, (vn –1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин – простой цепью. Замкнутый путь без повторяющихся ребер называется циклом (или
контуром в орграфе); без повторяющихся вершин (кроме первой и последней) – простым циклом.
Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным – в противном случае.
Существуют различные способы представления графов.
1. Матрица инцидентности.
Это прямоугольная матрица размерности n ч m, где n – количество вершин, а m – количество ребер.
2. Матрица смежности.
Это квадратная матрица размерности n ч n, где n – количество вершин.
3. Список смежности (инцидентности). Представляет собой структуру данных, которая
для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.
4. Список списков.
Представляет собой древовидную структуру данных, в которой одна ветвь содержит списки вершин, смежных для каждой.
