Способы задания графов
1. Граф - это система некоторых объектов вместе с некоторыми парами этих объектов, изображающая отношения связи между ними. Неориентированный граф(соответственно ориентированный граф, или орграф) G- система G = (V, E, Г), состоящая из множества элементов V= {v}, называемых вершинами графа, множества элементов Е = {е}, называемых ребрами, и отображения , ставящего в соответствие каждому элементу
неупорядоченную (соответственно упорядоченную) пару элементов
называемых концами ребра е.
Для неориентированного графа значение V1 и V2 может быть произвольным. Для ориентированного – V1 - начало пути, V2 - конец.
образует множество элементов графа; при этом предполагается, что
Отображение Г определяет отношение инцидентностиребра с каждым из своих концов. Для графа G = (V, Е, Г) употребляется также более короткое обозначение G = (V, Е) без указания инцидентностей, которые определяются контекстом.
Если - упорядоченная пара
при v1 - v2), то ребро е называется ориентированной дугой,исходящей из вершины v1 и входящей в вершину
;
называется началом, а
концом дуги е. Если
– неупорядоченная пара, то ребро е называется неориентированным.
Всякому графу G можно поставить в соответствие соотнесенный неориентированный граф с теми же множествами V и Е и инцидентностями, но все пары неупорядоченные.
Вершина, не инцидентная ни одному ребру, называется изолированной.Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми, или висячими.
Ребро с совпадающими концами называется петлей.
Две вершины, инцидентные одному и тому же ребру, называются соседними (или смежными). Два ребра, инцидентные одной и той же вершине, называются смежными.
Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными, или параллельными.
2. Графы могут различаться и не различаться. Обычно это связывают с понятием изоморфизма графов.
Два графа называются изоморфными, если существуют взаимно однозначные отображения сохраняющие инцидентность, т.е. е Є E1
3. Существует несколько способов задания графов:
1) Перечисление (список) ребер графа с указанием их концов и добавлением списка изолированных вершин.
2) Матрица инциденций графа с b вершинами и p ребрами- прямоугольная матрица с b строками и p столбцами, строки которой соответствуют вершинам графа, а столбцы - ребрам, причем j для неориентированного графа элемент матрицы
равен 1, если вершина
и ребро
инцидентны, и равен 0 в противном случае. Для ориентированного графа
если
является началом дуги
= +1, если v. - конец дуги
Вкаждом столбце матрицы инциденций -два ненулевых элемента, если ребро - не петля. Петле соответствует элемент, равный 2.
3) Матрица соседства (смежности) вершин графа с b вершинами- квадратная матрица размерности Ь, строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент
равен числу ребер, идущих из вершины
в вершину
(
не равно, вообще говоря,
, однако для неориентированных графов матрица соседства - симметричная). Для несмежных вершин соответствующий элемент матрицы равен 0.
4) Для наглядности граф часто представляют в виде геометрического объекта: вершинам соответствуют различные выделенные точки в пространстве (на плоскости), ребрам - отрезки кривых, связывающие соответствующие точки и не проходящие через выделенные точки, отличные от их концов.
5. Граф называется подграфом графа
обозначение:
если
и для множеств
сохраняются инциденции графа G. При этом, очевидно, каждое ребро из Е' входит в подграф Н вместе со своими концами.
Обычно рассматриваются только подграфы без изолированных вершин или только подграфы, содержащие все вершины графа (и только часть ребер); такие подграфы полностью определяются множеством своих ребер. В этих случаях можно естественным образом определить теоретико-множественные операции над подграфами: пересечение, объединение, симметрическую разность (называемую также суммой по модулю 2или просто суммой), дополнение до всего графа.