Навигация
1.2 Смежность
Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины. Если степень вершины равна 0, то получается изолированная графа. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом.
Пусть v1, v2 — вершины, е = (v1, v2) — соединяющее их ребро. Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается Г+( v ):
Г+( v ) : = { u Î V | (u, v) Î E}
Г( v ) : = Г*( v ) : = Г+( v ) È { v }
u Î Г( v ) Û v Î Г( u )
Замечание. Если не оговорено противное, то подразумевается Г+ и обозначается просто Г.
Если А Ì V — множество вершин, то Г (А) — множество всех вершин, смежных с вершинами из А:
Г (А) : = { u Î V | $v Î A u Î Г ( v )};
1.3 Другие определения
Часто рассматриваются следующие родственные графам объекты.
1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.
2. Если элементом множества Е может быть пара одинаковых (не различных)элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).
3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом.
4. Если элементами множества Е являются не обязательно двухэлементные, алюбые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.
5. Если задана функция Е: V ® М и/или F: Е® М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным).В качестве множества пометок обычно используются буквы или целые числа.
2. Способы задания графов
2.1 Изображение графа
Графы отображаются на плоскости набором точек и соединяющих их линий или векторов. При этом грани могут отображаться и кривыми линиями, а их длина не играет никакой роли.
Граф G называется плоским, если его можно отобразить в плоскости без пересечения его граней. Очертанием графа (face) считается любая топологически связанная область, ограниченная ребрами графа.
Неориентированный граф G = <V,E> называется связанным, если для любых двух узлов x,y О V существует последовательность ребер из набора E, соединяющий x и y. Граф G связан тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы обе граничные точки каждого ребра находились в одном и том же подмножестве. Граф G называется k-связным (k і 1), если не существует набора из k-1 или меньшего числа узлов V`Н V, такого, что удаление всех узлов V` и сопряженных с ними ребер, сделают граф G несвязанным.
Теорема Менгера: граф G является k-связанным тогда и только тогда, когда любые два различные узла x и y графа G соединены по крайне мере k путями, не содержащими общих узлов. k-связанные графы представляют особый интерес для сетевых приложений. Определенную проблему составляет автоматическое отображение графа на экране или бумаге. Кроме того, для многих приложений (например, CAD) все узлы графа должны совпадать с узлами технологической сетки. Возникают и другие ограничения, например необходимость размещения всех узлов на прямой линии. В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаные линии, состоящие из отрезков прямых.
2.2 Способы численного представления графа
1. Матричный способ (с помощью матрицы смежности). Матрица смежности имеет m – строк и n – столбцов, где m – количество вершин графа.
Элементами матрицы смежности являются 0 и 1, Если вершины соединены, то ставится 1 и наоборот.
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 1 | 1 |
| 3 | 1 | 0 | 0 | 0 | 1 |
| 4 | 1 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Матрица смежности графа GРис.
Похожие работы
... , "базовые" алгоритмы: поиск путей, определение компонент связности графа и т.д. 8. Ввод/вывод графов Одной из проблем при создании средств работы с помеченными графами является выбор внешнего файлового формата для хранения графов. До недавнего времени каждая программная система использовала свой собственный, уникальный формат, что приводило к сложностям при организации обмена данными. ...
... write(fileKlics,klika); end; end; end; {конец пеpебоpа возможных мест в стpоке} end; {конец пpохода по стpокам} close(fileklics); end; Выше представлена процедура нахождения клик в графе. Описание переменных: StolbecSravn: номер сравниваемого столбца. StringSravn: номер текущей строки. Num ,i1,i: счетчики. lenStolb: размер множества вершин клики. Stolbec: номер столбца первой ...
... . Вся процедура поиска представлена ниже (данная процедура используется также и для просмотра графа, и в псевдокоде, описанном ниже, отсутствуют операторы, которые не используются для поиска). 1 procedure WS (v); (*поиск в ширину в графе с началом в вершине v; переменные НОВЫЙ, ЗАПИСЬ — глобальные *) 2 begin 3 ОЧЕРЕДЬ := Æ; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь 4 while ОЧЕРЕДЬ &# ...
... файла из которого будет происходить ввод X – грав в последовательном представлении O(N,N1)=N2 N2 – количество вершин в графе X Текст программы. # include # include # include # include # include # include /////////////////////////////////////////////////////////////////////////////////////////////////////// struct Spisok //Связанное представление графа { int index; //Содержвтельная " ...
0 комментариев