Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




Пусть G – помеченный граф с n вершинами и m ребрами. Определим матрицу смежности A(G) следующим образом:

Матрица смежности квадратная, размера n ´ n.

Пример 4.5.

 

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

Пример 4.6. Построить граф по матрице смежности

v1
v2
v3
v4
v5
v6

 

Можно определить матрицу инцидентности I(G), имеющую n строк и m столбцов, элементы которой задаются следующим образом:

 

Пример 4.7. Рассмотрим граф из примера 4.6, обозначив ребра.

v2
e1
v1
v3
v4
v5
v6
e2
e3
e4
e7
e5
e6

 

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

Пример 4.8. Рассмотрим граф из примера 4.7. Список ребер имеет вид:

, , , , , , .

По списку ребер графа легко построить матрицу инцидентности, т.к. каждое ребро этого списка соответствует столбцу матрицы, а номера вершин в каждом элементе списка – это номера элементов строки матрицы инцидентности, которые равные 1.

Граф может быть представлен различными способами. Иногда не легко понять, одинаковы ли графы, изображенные разными чертежами или разными матрицами. Графы, отличающиеся только нумерацией вершин, называются изоморфными. Перенумерация задается строкой новых номеров вершин, расположенных в исходном порядке. Новая матрица смежности получается в результате перемещения каждого элемента aij в строку и столбец, т.е. в результате перестановки ( ) строк и столбцов исходной матрицы. Можно выполнить все возможные перестановки строк и столбцов для того, чтобы убедиться в неизоморфности графов, но это потребует n! перестановок, что достаточно трудоемко.


Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой





Дата добавления: 2015-09-18; просмотров: 548. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.017 сек.) русская версия | украинская версия
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7