Виды графов и операции над ними реферат
Обновлено: 05.07.2024
Графы. Основные определения. Элементы графов. Виды графов и операции над ними.
Методические указания по теме 2.2:
Графы. Основные определения. Элементы графов:
Графом G(V, Е) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов
множества V (Е — множество ребер).
Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки. Число вершин графа A обозначим р, а число ребер – q:
p : = p ( A ) : = | V |, q : = = q ( A ) : = | E |;
Более простое определение графа - совокупность точек и линий, в которой каждая линия соединяет VÍдве точки. Для ориентированного графа E x - конечный набор ориентированных ребер. Ребром может быть прямая или кривая линия. Ребра не могут иметь общих точек кроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку из множества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V. Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер. Параллельными ребрами графа называются такие, которые имеют общие узлы начала и конца. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины. Если степень вершины равна 0, то получается изолированная графа. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом.
Пусть v1, v2 — вершины, е = (v1, v2) — соединяющее их ребро. Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается Г + ( v ).
Часто рассматриваются следующие родственные графам объекты:
1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.
2. Если элементом множества Е может быть пара одинаковых (не различных)элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).
3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом.
4. Если элементами множества Е являются не обязательно двухэлементные, алюбые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.
5. Если задана функция Е: V ® М и/или F: Е® М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.
Виды графов и операции над ними:
Для рассмотрения видов граф и операций над ними необходимо познакомиться с такими понятиями как подграфы, маршрут, цепь, цикл.
Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G' Ì G), если V' Ì V и/или Е' Ì Е. Если V' = V, то G ' называется остовным подграфом G. Если V' Ì V & Е' Ì Е & (V' ¹ V Ú Е' ¹ Е), то граф G ' называется собственным подграфом графа G. Подграф G'(V' , Е') называется правильным подграфом графа G(V,Е), если G ' содержит все возможные ребра G.
Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.
Элементы графа – любое чередование вершин и рёбер графа, в котором каждому ребру предшествует смежная ей вершина, называющаяся контуром графа.
Два графа G1(V1 , Е1) и G2(V2 , Е2) изоморфны (обозначается G1 ~ G2), если существует биекция h: V1 ® V2, сохраняющая смежность: e1 = ( u , v ) Î E1 Þ e2 = ( h( u ), h( v ) ) Î E2,
e2 = ( u , v ) Î E2 Þ e1 = ( h -1 ( u ), h -1 ( v ) ) Î E1.Изоморфизм графов есть отношение эквивалентности.
Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа.
Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с k вершинами, обозначается Сk.
Граф, в котором каждая пара вершин смежная, называется полным. Полный граф с р вершинами обозначается Кр, он имеет максимально возможное число ребер. Полный подграф (некоторого графа) называется кликой (этого графа).
Двудольный граф (или биграф, или четный граф) — это граф G(V,Е), такой что множество V разбито на два непересекающихся множества V1 и V2 (V1 ÈV2 = V& V1 Ç V2) причем всякое ребро из Е инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2). Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом. Если | V1 | = m и | V1 | = п, то полный двудольный граф обозначается Km,n Если в графе ориентировать все ребра, то получится орграф, который называется направленным. Направленный орграф, полученный из полного графа, называется турниром.
Над графами можно выполнять следующие операции:
4. Удаление ребра e из графа G1(V1 , Е1)(обозначение - G1(V1 , Е1) – e, при условии e Î E1) даёт граф G2(V2 , Е2), где V2 : = V1 & E2 : = E1 \
6. Добавление ребра e в граф G1(V1 , Е1) (обозначение - G1(V1 , Е1) + v, при условии e Ï E1) даёт граф G2(V2 , Е2), где V2 : = V1 & E2 : = E1 È
7. Стягивание подграфа А графа G1(V1 , Е1) (обозначение - G1(V1 , Е1) / А, при условии А Ì V1) даёт граф G2(V2 , Е2), где V2 : = (V1 \ A) È &
Вопросы для самопроверки по теме 2.2:
1.Что такое граф?
2.Что относится к элементам графа?
3.Перечислить виды графов.
4. Какие операции можно выполнять над графами?
Задания для самостоятельного решения по теме 2.2:
1.Нарисуйте граф со смежными вершинами, ребрами, петлей. Подсчитайте сумму степеней всех его вершин.
Читайте также: