|
Определение. Матрица C=[cij], у которой cij {0,1} наз. булевой.
Если G – псевдограф без кратных ребер, матрица смежности – булева.
Контрольные задания:
Покажите, что в любом графе количество вершин нечетной степени
четно.
Можно ли выделить простую цепь из всякого замкнутого маршру-та нечетной длины?
Покажите, что ребро, входящее в цикл графа, входит в некоторый его простой цикл.
Докажите, что любая вершина, входящая в цикл графа, не является висячей.
Определите матрицы достижимости и сильной связности для ор-графов с матрицами смежности из задачи 5.
Нарисуйте соответствующие графы для заданных матриц:
а)
|
|
|
|
|
|
|
|
|
|
|
x1
|
x2
|
|
|
|
|
v1
|
1
|
1
|
|
|
|
|
v2
|
1
|
0
|
|
|
|
|
v3
|
0
|
1
|
|
|
|
б)
|
|
|
|
|
|
|
|
|
|
v1
|
|
v2
|
v3
|
|
|
v1
|
|
1
|
|
2
|
0
|
|
|
v2
|
|
0
|
|
0
|
0
|
|
|
v3
|
|
2
|
|
3
|
2
|
|
Лекция 15. Способы задания графов. Матрицы смежности и инцидентности (2 часа)
План:
1. Способы задания графов.
2. Матрицы смежности и инцидентности.
Ключевые слова: аналитический способ, графический способ, матрица смежности, матрица инцидентности.
1. Способы задания графов.
Графы можно задавать различными способами: аналитическим, гра-фическим и матричным.
При аналитическом способе перечисляются множества V и X, на-Пример. G = (V, X), V = {a, b, c}, X = {{b, a}, {b, c}, {c, a}}.
При графическом способе все элементы множества V обозначаются точками (или кружками) на плоскости, и если {vi, vj}∈X, то проводится ли-ния, соединяющая вершины vi и vj (Рисунок 1).
При матричном способе применяются матрицы смежности и инцидентности.
Замечания: 1. Понятие матрицы смежности для неориентированного графа такое же. Отличие состоит лишь в том, что матрица смежности для графа симметричная, для орграфа – нет.
Матрицу смежности можно определить и для псевдографа. Тогда ai, j = k, где k – кратность дуги (vi, vj) (или ребра).
2. Матрицы смежности и инцидентности.
Пусть D=(V,X) ориентированный граф, V={v1,...,vn}, X={x1,...,xm}.
Матрица смежности ориентированного графа D − квадратная матрица
A(D)=[aij] порядка n, где
Матрица инцидентности − матрица B(D)=[bij] порядка nm, где
Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[aij] порядка n, где
Матрица инцидентности графа G называется матрица B(G)=[bij] порядка nm, где
Графы G1(V1, X1) и G(V2, X2) называются изоморфными, если существует биекция f: V1→V2, такая, что выполнено:
При этом f называется изоморфизмом графов G1 и G2. Изоморфизм графа G на себя называется автоморфизмом.
Примеры решения типовых задач
Таблица 1.
Таблица 2.
Пример. Задать матрицами инцидентности и смежности, а также списком ребер графы G1, G3 см. Рисунок 2.
Рисунок 2.
Матрицы инцидентности графов G1 и G3 приведены в табл. 1. В матрице инцидентности в каждом столбце только два элемента, отличных от 0 (или один, если ребро – петля). Список ребер является более компактным описанием графа. Матрицы смежности графов G1, G3 даны в табл. 2
Таблица 3 Таблица 4
Пример. На рисунке 3 изображен сетевой граф (сетевая модель) выполнения комплекса операций (работ) некоторой программы. В нем стрелки обозначают операции, вершины - события, характеризующие окончание одних работ и начало других. Направленность стрелок отражает последовательность наступления этих событий.
Задать сетевой граф различными способами:
Рисунок 3
Изображенная сетевая модель представляет собой ориентированный граф, который может быть полностью задан различными способами:
1) графически (см. Рисунок 3);
2) с помощью задания двух множеств: V={1,2,3,4,5,6} и E={(1,2),(1,3),(2,4),(2,5),(3,4),(4,6),(5,6)};
3) матрицей инцидентности (см. табл. 3). Особенностью сетевой модели является то, что из начального события 1 стрелки только выходят, а в конечное 6 - только входят. Поэтому в первой строке матрицы инцидентности имеются единицы только со знаком "минус", а в последней - только со знаком "плюс";
4) матрицей смежности см. табл. 4. По причине, указанной в п. 3, в последней строке матрицы смежности проставлены только нули;
5) списком ребер сетевой граф задается очевидным образом, поскольку ребра графа обозначены через свои концевые вершины. В таком случае в столбце "вершины" списка будут повторяться номера вершин, указанных в столбце "ребра", причем в той последовательности, в какой в данном случае стрелки-ребра обозначены.
Контрольные задания.
Рисунок 4 (а, б, в, г)
Рисунок 5 (а, б, в) Рисунок6
Задать графы G1-G5, изображенные на рисунке 5, матрицами инцидентности и смежности, а также списком ребер.
Задать различными способами графы G1-G7, определенные ниже. Проверить справедливость правил переходов от одного способа задания графа к другому:
G1 - тетраэдр;
G2 - тетраэдр с петлями во всех вершинах;
G3 - кy6;
G4 - граф, представленный на Рисунок 4, а;
G5-граф на Рисунок 4, б;
G6 -граф на Рисунок 4, в;
G7 - граф на Рисунок 4, г;
Представленные на рисунке 5 графы задать матрицами смежности. Определить, изоморфны ли эти графы.
Показать, что 2 графа на рисунке 6 изоморфны.
Д ан граф. Написать для него матрицы смежности и инцидентности.
Задать граф, состоящий из 8 ребер и 9 вершин, графически, списком ребер и вершин, а также с помощью матриц смежности и инцидентности.
Даны матрица смежности и инцидентности. Построить по ним граф.
Матрица смежности Матрица инцидентности
Do'stlaringiz bilan baham: |
