Матричные способы задания графа

Матричные способы задания графов. Упорядочение элементов орграфа

При большом числе элементов рисунок графа теряет наглядность. В таком случае граф целесообразно задать матричным способом. Этот способ также удобен и для решения задачи на компьютере.

Определение 12.3. Матрицей инцидентности орграфа без петель с n вершинами и m дугами называется матрица, любой элемент которой определяется по следующей формуле:

Для неориентированного графа вместо «–1» ставится «1».

Пример.Для заданного ориентированного графа (рис. 12.10) построить матрицу инцидентности:

Матрица инцидентности орграфа:

.

Определение 12.4. Матрица смежности вершин орграфа – квадратная матрица n-го порядка (n – число вершин). Строки и столбцы матрицы соответствуют вершинам графа. Элементы S_ij матрицы равны числу дуг, направленных из i-й вершины в j-ю.

В случае неориентированного графа ему вместе с ребром (x_i,x_j) принадлежит и ребро (x_j,x_i), поэтому матрица будет симметрической.

Пример.Для заданного ориентированного графа (рис. 12.11) построить матрицу смежности вершин:

Матрица смежности вершин орграфа:

.

Определение 12.5. Матрица смежности дуг орграфа – квадратная матрица m-го порядка (m – число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы q_ij равны 1, если дуга u_i непосредственно предшествует дуге u_j, и нулю в остальных случаях.

Для неориентированного графа матрица смежности дуг симметрическая с элементами равными 1, если ребра имеют общую вершину, и 0 в остальных случаях.

Пример.Для заданного ориентированного графа (рис. 12.12) построить матрицу смежности дуг:

Матрица смежности дуг орграфа:

.

Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.

Определение 12.6. Вершина x_i предшествует вершине x_j, если существует путь из x_i в x_j, тогда x_i называется предшествующей вершине x_j, а x_j – последующей за x_i.

Под упорядочением вершин связного орграфа без контуров понимают такое разбиение его вершин на группы, при котором:

1) вершины первой группы не имеют предшествующих, а вершины последней – последующих;

2) вершины любой другой группы не имеют предшествующих в следующей группе;

3) вершины одной и той же группы дугами не соединяются.

В результате упорядочения элементов получают граф, изоморфный данному.

Графический способ упорядочения вершин – алгоритм Фалкерсона:

1) Находят вершины графа, в которые не входит ни одна дуга. Они образуют первую группу.

2) Вершины и исходящие из них дуги исключают из дальнейшего рассмотрения (то есть вычеркивают).

3) Устанавливается следующая группа вершин, в которую не входит ни одна дуга. Этот шаг повторяют до тех пор, пока все вершины не будут упорядочены.

Пример.Упорядочить вершины орграфа (рис. 12.13):

Упорядочим вершины орграфа по алгоритму Фалкерсона (рис. 12.14):

Дата добавления: 2014-12-03 ; просмотров: 340 ; Нарушение авторских прав

Источник

Матричные способы задания графов

Для алгебраического задания графов используются матри­цы смежности и инцидентности.

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

a_ij =

Матрица смежности графа, изображенного на рис. 3.1, имеет вид:

A =

Матрица смежности ориентированного графа, изображенного на рис. 3.2, имеет вид:

A =

Матрица смежности полностью задает граф.

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

b_i =

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

b_i =

Матрица инцидентности графа, изображенного на рис. 3.1, имеет вид:

B =

Матрица инцидентности ориентированного графа, изображенного на рис. 3.2, имеет вид:

B =

Матрица инцидентности, также, как и матрица смежности, полностью задает граф.

Матрицы смежности и инцидентности удобны для задания графов на ЭВМ.

Основные свойства матриц смежности и инцидентности

1. Матрица смежности неориентированного графа является симметрич­ной. Для ориентированного графа это, вообще говоря, неверно.

2. Сумма элементов i — ой строки или i -го столбца матрицы смежности неориентиро­ванного графа равна степени вершины x_i.

3. Сумма элементов i — ой строки матрицы смежности ориентиро­ванного графа равна числу дуг, исходящих из x_i.

4. Сумма элементов i — го столбца матрицы смежности ориентиро­ванного графа равна числу дуг, входящих в вершину x_i.

5. Сумма строк матрицы инцидентности ориентированного графа явля­ется нулевой строкой.

Итак, возможны следующие различные способы задания графа:

а) посредством графического изображения;

б) указанием множества вершин и множества ребер (дуг);

в) матрицей смежности;

г) матрицей инцидентности.

Изоморфизм графов

Графы G₁= (X₁, A₁)и G₂= (X₂, A₂) изоморфны, если существует взаимно однозначное соответствие между множествами вершин X₁и X₂, та­кое, что любые две вершины одного графа соединены тогда и только тог­да, когда соответствующие вершины соединены в другом графе.

Графы, изображенные на рис. 3.4 являются изоморфными.

Изоморфные графы отличаются только нумерацией вершин. Матрицы смежности двух изоморфных графов могут быть получены одна из другой перестановкой строк и столбцов. Чтобы узнать, являются ли два графа изоморфными, нужно произвести все возможные перестановки строк и столбцов матрицы смежности одного из графов. Если после какой-нибудь перестановки получится матрица смежности второго графа, то эти графы изоморфны. Чтобы убедиться, что графы неизоморфны, надо выполнить все n! возможных перестановок строк и столбцов.

Источник

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

Рассмотрим три способа задания графов: графический, аналитический и матричный.

1) Графический способ.

Вершины изображают точками на плоскости, а ребра – линиями, соединяющими соответствующие точки. Для изображения дуги используется линия со стрелкой, указывающей направление от начала к концу дуги.

На рисунке 12 изображен смешанный граф с вершинами v₁, v₂,¼, v₆, ребрами e₁, e₂, e₃, e₅ и дугой e₄. Смежные вершины v₁, v₂, инциденты ребру e₁. Вершины v₁, v₃, инциденты параллельным ребрам e₂ и e₃. Вершине v₄ инциденты петля e₅ и дуга e₄, причем v₄ является началом дуги e₄, а v₅ – концом этой дуги. Степень вершины v₁ равна 3, вершины v₂ – 1, вершины v₃ – 2, вершины v₄ – 3, вершины v₅ – 1, вершины v₆ – 0. Таким образом, вершины v₂ и v₅ – висячие, а вершина v₆ – изолированная. В случае дуги e₄ точнее было бы говорить о полустепенях исхода и захода вершин v₄ и v₅, а именно: полустепень исхода вершины v₄ равна 3, вершины v₅ – 0, полустепень захода вершины v₄ равна 2, вершины v₅ – 1.

2) Аналитический способ.

3) Матричный способ.

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

а) Матрица инциденций – это прямоугольная матрица, число строк которой равно числу вершин, а число столбцов – числу дуг (ребер) графа. Элементы этой матрицы определяются следующим образом:

Таким образом, для графа на рисунке 12 матрица инциденций такова:

Читайте также: B.6.4.1. Способы выделения текста. III. Для обеспечения проверки исходного уровня знаний-умений решите 2 задания. III. Для обеспечения проверки исходного уровня знаний-умений решите 2 задания. III. Для обеспечения проверки исходного уровня знаний-умений решите 2 задания. V. Способы и методы обеззараживания и/или обезвреживания медицинских отходов классов Б и В VII. Выполнение задания на развитие внимания, смекалки. VII.2.2) Способы приобретения права собственности. XII. Способы оплаты труда Алгоритм. Свойства алгоритма. Способы описания алгоритма. Примеры. Амортизация ОС. Способы

e1	e2	e3	e4	e5
v1
v2
I=	v3
v4
v5	-1
v6

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

б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так: . Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Так матрица смежности для графа на рисунке 12 такова:

v1	v2	v3	v4	v5	v6
v1
v2
S=	v3
v4
v5
v6

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

Дата добавления: 2015-10-19 ; просмотров: 17468 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник

Геометрический способ задания графов

Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину соединяют линиями с теми вершинами , для которых выполняется условие Множество линий, которое соответствует множеству упорядоченных пар есть множество рёбер.

Матричный способ задания графов

Квадратная матрица элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа тогда и только тогда, когда её элементы образуются по следующему правилу: элемент стоящий на пересечении й строки и го столбца, равен единице, если имеется ребро, идущее из вершины в вершину и равен нулю в противном случае. Элемент равен единице, если при вершине имеется петля, и равен нулю в противном случае. Элемент равен некоторому числу m, где m – число рёбер графа, идущее из вершины в вершину

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

Инструкция к практической работе

Задание 1. Изобразите графически:

1. Неориентированное и ориентированное ребро;

4. Полный неориентированный граф на трех, четырех и пяти вершинах;

5. Неполный ориентированный граф на пяти вершинах;

7. Неориентированный и ориентированный мультиграф.

Решение:

1) Неориентированное ребро ориентированное ребро

Задание 2. Изобразить графы в программах:

grin_rus, Grafoanalizator1.3.3 rus, windisc ru.

Задание:

Вариант № 1

Задание 1. Выполните задание по образцу.

G ( V , E ) — орграф.

Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.

Граф	Программа
	Grafoanalizator1.3.3 rus
	grin_rus
	windisc ru

Вариант № 2

Задание 1. Выполните задание по образцу.

G ( V , E ) — орграф.

Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.

Граф	Программа
	Grafoanalizator1.3.3 rus
	grin_rus
	windisc ru

Вариант № 3

Задание 1. Выполните задание по образцу.

G ( V , E ) — орграф.

Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.

Граф	Программа
	Grafoanalizator1.3.3 rus
	grin_rus
	windisc ru

Вариант № 4

Задание 1. Выполните задание по образцу.

G ( V , E ) — орграф.

Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.

Граф	Программа
	Grafoanalizator1.3.3 rus
	grin_rus
	windisc ru

Порядок выполнения работы:

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.

Содержание отчета:

4. Материальное обеспечение.

5. Практическое задание.

Вопросы для самоконтроля:

1.Что называется графом? Ориентированным графом? Приведите примеры.

2.Что такое степень вершины?

3.Перечислите основные понятия, связанные с неориентированными графами.

4.Перечислите основные понятия, связанные с орграфами.

5.В чем состоит аналитический способ задания графа?

6.В чем состоит геометрический способ задания графа?

7.В чем состоит матричный способ задания графа?

8.Что называется маршрутом, циклом и цепью графа?

9.Сформулируйте понятие связности графа. Какой граф называют связным?

10.Какие два графа называются изоморфными?

11.Сформулируйте алгоритм изоморфизма двух графов.

12.Перечислите операции над графами.

Практическая работа № 2,3

Тема: Решение задач по теории графов. Эйлеровы и Гамильтоновы графы.

Цель: изучить алгоритмпоиска эйлерова, гамильтонова цикла (пути) в графе, рассмотреть на конкретных примерах ориентированные и неориентированные графы.

Задачи:

1. Закрепить знания основных понятий теории графов.

2. Приобрести практические умения использования специального программного обеспечения для моделирования.

3. Использовать математический аппарат теории графов

Материальное обеспечение:

Программа анализатор графов: Grafoanalizator1.3.3 rus, практическое задание.

Теоретическая часть:

Эйлеровы графы

К задачам на Эйлеровы графы относятся головоломки, в которых требуется вычертить на плоскости одним росчерком замкнутые кривые, обводя каждый участок в точности один раз. Введём следующие понятия.

Эйлеровым путём в графе называется путь, содержащий все рёбра графа.

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

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Замкнутую линию, если её можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, принято называть уникурсальной.

Рисунок графа, обладающий эйлеровым путём или эйлеровым циклом, является уникурсальной линией.

Докажем следующие две теоремы

Теорема 1. Если граф обладает эйлеровым циклом, то он связный и все его вершины четные.

Доказательство. Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз эйлеров путь приведет конец карандаша в вершину, столько и выведет, причём уже по одному ребру. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: одно – результат подсчета входов в вершину, другое – выходов.

Теорема 2. Если граф связный и все его вершины четные, то он обладает эйлеровым циклом.

Доказательство. Если начать путь из произвольной вершины графа , то найдётся цикл, содержащий все рёбра графа. Пусть — произвольная вершина. Из начнём путь по l по одному из рёбер и продолжим его, проходя каждый раз по новому ребру. Все вершины графа имеют чётные степени, поэтому если l есть «выход» из , то должен быть и «вход» в , также как и для любой вершины другой вершины. И если есть «вход» в вершину, то должен быть и «выход». Так как число ребер конечно, то это путь должен окончиться, причём в вершине . Если путь, замкнувшийся в , проходит через все рёбра графа, то мы получим искомый эйлеров цикл.

Для построения эйлерова цикла в связном графе со всеми вершинами чётной степени применяется следующий алгоритм:

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

2. Если остались непройденные рёбра, то должна существовать вершина принадлежащая и ребру, не вошедшему в

3. Так как чётная, то число рёбер, которым принадлежит и которые не вошли в путь тоже чётно. Начнём новый путь из и используем только рёбра, не принадлежащие Этот путь кончится в

4. Объединим теперь оба цикла: из пройдём по пути к затем по и, вернувшись в пройдём по оставшейся части обратно в .

5. Если снова найдутся рёбра, которые не вошли в путь, то найдём новые циклы. Так как число рёбер и вершин конечно, то процесс закончится.

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

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

Гамильтоновы графы

Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

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

Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все рёбра, и притом по одному разу, вторые – все вершины по одному разу. Но, несмотря на внешнее сходство, задачи их отыскания резко отличаются по степени трудности. Для решения вопроса о существовании эйлерова цикла в графе достаточно выяснить, все ли его вершины чётные.

Критерий же существования гамильтонова цикла на произвольном графе ещё не найден.

Однако есть несколько достаточных условий существования гамильтоновых циклов в графе:

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

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

3. Если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.

Дата добавления: 2019-02-22 ; просмотров: 2930 ; Мы поможем в написании вашей работы!

Источник