Пояснение к работе

Практическое занятие № 5

Тема: «Элементы графа. Способы задания графа. Подграфы.

Изоморфизм»

Цель занятия:

усвоение таких понятий, как граф, вершины и ребра графа, ориентированный и неориентированный граф, мультиграф, псевдограф, смежность, инцидентность, изоморфизм, матрицы смежности и инцидентности, двудольный граф, полный граф, подграф, степень вершины.

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какие вершины графа называются смежными?

В чем заключается понятие инцидентности?

Как задается матрица инциденций для орграфа?

Какой граф называется псевдографом?

Какой граф называется двудольным?

2. Дать определение следующих понятий:

– граф;

– изоморфизм;

– полный граф;

– подграф;

– ориентированный граф.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

5.1. Элементы графа

Граф G – это совокупность двух множеств: непустого множества вершин V = { v ₁, v ₂,..., v_n } и множества ребер (дуг) Е = { е ₁, е ₂,..., е_n }. Таким образом, G = (V, Е), V ¹ Æ, Е Ì V × V.

Если (v ₁, v ₂) – упорядоченная пара (т. е. дуга), то v ₁ называется началом, a v ₂ – концом дуги е. Если { v ₁, v ₂} – неупорядоченная пара, то ребро е называется неориентированным. Всякому графу G можно поставить в соответствие соотнесенный неориентированный граф G с теми же множествами V и Е и инцидентностями, но все пары неупорядоченные. Такой граф называется ассоциированным. Вершина, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми или висячими. Ребро с совпадающими концами называется петлей. Две вершины, инцидентные одному и тому же ребру, называются смежными. Два ребра, инцидентные одной и той же вершине, называются смежными. Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными или параллельными.

Граф, содержащий кратные ребра, называется мультиграфом. Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины. Граф с кратными ребрами и петлями называется псевдографом.

e₆

Примеры:

Рис. 3

На рис. 3 изображены: ориентированный псевдограф, имеющий 7 вершин и 6 дуг, и неориентированный мультиграф, имеющий 4 вершины и 5 ребер. Проиллюстрируем некоторые введенные понятия.

Для орграфа (рис. 3 а): v ₁, v ₂, v ₃, v ₄, v ₅, v _6, v ₇ – вершины (узлы); v ₅ – изолированная вершина; v ₁, v ₄ – концевые (висячие) вершины; v ₂ и v ₃, v ₂ и v ₁ –пары соседних вершин; е ₁, е ₂, е ₃, е ₄, е ₅, е ₆ – ориентированные ребра (дуги); е ₂ и е ₃ – параллельные (кратные) дуги; е ₂ и е ₁ – смежные дуги; е ₆ –петля для орграфа.

Для графа (рис. 3 б): v ₁, v ₂, v ₃, v ₄ – вершины; v ₄ – концевая (висячая) вершина; v ₂ и v ₃, v ₂ и v ₁ –пары соседних вершин; е ₁, е ₂, е ₃, е ₄, е ₅ – ребра (дуги); е ₄ и е ₅ – параллельные (кратные) ребра; е ₂ и е ₃ – смежные ребра; петель нет.

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

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

2. Матрица смежности A = ( a_ij)определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n – число вершин, у которой

a_ij =

Матрицей инцидентности B = (b_ij) ориентированного графа называется матрица (n ´ m), где n – число вершин, m – число ребер, у которой

b_ij =

Для неориентированного графа матрица инцидентности B задается следующим образом:

b_ij =

Петле соответствует элемент, равный 2.

Пример.

Матрицы смежности и инцидентности графа, изображенного на рис. 3 а, имеют вид (рис. 4):

Дата добавления: 2017-02-01