Способы задания графов.

 

1. Граф  - это система некоторых объектов вместе с некоторыми парами этих объектов, изображающая отношения связи между ними. Неориентированный граф(соответственно ориентированный граф, или орграф) G- система G = (V, E, Г), состоящая из множества элементов V= {v}, называемых вершинами графа, множества элементов Е = {е}, называемых ребрами, и отображения , ставящего в соответствие каждому элементу неупорядоченную (соответственно упорядоченную) пару элементов называемых концами ребра е.

  Для неориентированного графа значение V₁ и V₂ может быть произвольным. Для ориентированного  –  V₁ - начало пути, V₂ - конец.

 образует множество элементов графа;  при этом предполагается, что

Отображение Г определяет отношение инцидентностиребра с каждым из своих концов. Для графа G = (V, Е, Г) употребляется также более короткое обозначение G = (V, Е) без указания инцидентностей, которые определяются контекстом.

 

Если - упорядоченная парапри v₁ - v₂), то ребро е называется ориентированной дугой,исходящей из вершины v₁ и входящей в вершину ; называется началом, а  концом дуги е. Если – неупорядоченная пара, то ребро е называется неориентированным.

Всякому графу G можно поставить в соответствие соотнесенный неориентированный граф с теми же множествами V и Е и инцидентностями, но все пары неупорядоченные.

Вершина, не инцидентная ни одному ребру, называется изолированной.Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми, или висячими.

Ребро с совпадающими концами называется петлей.

Две вершины, инцидентные одному и тому же ребру, называются соседними (или смежными). Два ребра, инцидентные одной и той же вершине, называются смежными.

Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными, или параллельными.

 

2. Графы могут различаться и не различаться. Обычно это связывают с понятием изоморфизма графов.

Два графа называются изоморфными, если существуют взаимно однозначные отображения сохраняющие инцидентность, т.е. е Є E₁

                               

 

3. Существует несколько способов задания графов:

1)  Перечисление   (список) ребер графа с указанием их концов и добавлением списка изолированных вершин.

2)  Матрица инциденций                      графа с b вершинами и p ребрами- прямоугольная матрица с b строками и p столбцами, строки которой соответствуют вершинам графа,  а столбцы - ребрам, причем j для неориентированного графа элемент матрицы равен 1, если вершинаи ребро инцидентны, и равен 0 в противном случае. Для ориентированного графаеслиявляется началом дуги= +1, если v. - конец дуги В каждом столбце матрицы инциденций -два ненулевых элемента, если ребро - не петля. Петле соответствует элемент, равный 2.

3)  Матрица соседства  (смежности)  вершин  графа с b вершинами- квадратная матрицаразмерности Ь, строки и столбцы   которой   соответствуют   вершинам   графа,   причем неотрицательный элементравен числу ребер, идущих из вершиныв вершину(не равно, вообще говоря, , однако для неориентированных графов матрица соседства - симметричная). Для несмежных вершин соответствующий элемент матрицы равен 0.

4)   Для   наглядности   граф   часто   представляют   в   виде геометрического объекта: вершинам соответствуют различные выделенные  точки   в  пространстве (на плоскости), ребрам - отрезки кривых, связывающие соответствующие точки и не проходящие через выделенные точки, отличные от их концов.

5. Граф называется подграфом графа обозначение:еслии для множеств сохраняются инциденции графа G.  При этом, очевидно, каждое ребро из Е' входит в подграф Н вместе со своими концами.

Обычно рассматриваются только подграфы без изолированных вершин или только подграфы, содержащие все вершины графа (и только часть ребер); такие подграфы полностью определяются множеством своих ребер. В этих случаях можно естественным образом определить теоретико-множественные операции над подграфами: пересечение, объединение, симметрическую разность (называемую также суммой по модулю 2или просто суммой), дополнение до всего графа.

Подграфом, натянутым на множество вершинграфа

G,называется подграф, содержащий вершины из V и все ребра графа G, соединяющие пары вершин из

Подграф, состоящий из всех ребер, инцидентных вершине называется звездой вершины

Для графов без петель степеньвершиныα есть число ребер в звезде Zα. Очевидно, что сумма степеней всех вершин графа без петель равна удвоенному числу ребер.