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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Реферат Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.

Информация:

Тип работы: Реферат. Предмет: Математика. Добавлен: 23.11.2008. Сдан: 2008. Уникальность по antiplagiat.ru: --.

Описание (план):


БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
«Матрицы графов»

МИНСК, 2008
В теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, - любая матрица графа может быть введена в ЭВМ.
При задании графов в матричной форме могут учитываться либо отношения смежностей (вершин или ребер (дуг)), либо отображения инцидентности (вершин и ребер (дуг)). В связи с этим матрицы графов делятся на два основных класса: матрицы смежностей и матрицы инциденций.
Определение.1. Матрицей смежности вершин неориентированного графа G называется квадратная матрица A(G)=aij порядка p=p(G) (p - количество вершин графа), элементы aij которой равны числу ребер, соединяющих вершины xi и xj.
x1
x2
x3
x4
x5
x6
x7
x8
x1
2
0
0
0
1
0
1
0
x2
0
0
1
0
0
1
1
0
x3
0
1
0
1
0
1
0
0
A(G)
=
x4
0
0
1
0
1
0
0
0
x5
1
0
0
1
0
0
0
1
x6
0
1
1
0
0
0
0
0
x7
1
1
0
0
0
0
0
0
x8
0
0
0
0
1
0
0
0
На рис. 1 приведен неориентированный граф G(X, E) и справа - соответствующая ему матрица смежностей вершин A(G).
Из определения 1 непосредственно вытекают основные свойства матриц этого вида.
1. Матрица смежностей вершин неориентированного графа A(G) является квадратной и симметричной относительно главной диагонали.
2. Элементами матрицы A(G) являются целые положительные числа и число ноль.
3. Сумма элементов матрицы A(G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины (xi).
Из определения матрицы смежностей вершин неориентированного графа и ее основных свойств следуют некоторые особенности соответствия между графом G(X, E) и его матрицей A(G). На рис. 1 указана некоторая нумерация вершин графа; расположенная рядом матрица соответствует именно этой нумерации. Если же в графе G(X, E), приведенном на этом рисунке, использовать другую нумерацию вершин (например, сдвинув ее относительно вершин по часовой стрелке), то это приведет к тому, что в матрице A(G) произойдет перестановка отдельных строк и столбцов. Поэтому говорят, что каждый неориентированный граф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная симметричная относительно главной диагонали матрица, элементами которой являются целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма неориентированный граф, матрицей смежностей вершин которого является данная матрица.
Рекомендуется самостоятельно построить матрицу смежностей вершин графа G(X, E), показанного на рис. 1, с использованием другой нумерации вершин и сравнить полученную при этом матрицу с матрицей смежностей вершин приведенного графа.
Определение 2. Матрицей смежности вершин ориентированного графа G называется квадратная матрица A(G)=aij порядка n (n - число вершин графа), элементы которой aij равны числу дуг, исходящих из вершины xi и заходящих в вершину xj.
x1
x2
x3
x4
x5
x6
x7
x8
x1
0
0
0
0
0
0
0
0
x2
0
0
0
0
0
1
0
0
x3
0
1
0
0
1
0
1
0
A(G)
=
x4
1
0
0
0
0
0
0
0
x5
0
0
0
0
1
1
0
0
x6
0
0
0
0
0
0
0
1
x7
0
0
0
0
0
1
0
0
x8
1
0
0
0
1
0
0
0
На рис. 2 показан ориентированный граф G(X, E) и справа - матрица смежностей его вершин. Из определения следует, что сумма элементов i-й строки матрицы A(G) орграфа равна полустепени исхода +(xi), а по i-му столбцу - полустепени захода -(xi). По-прежнему элементы этой матрицы - целые положительные числа и число ноль. Матрица смежностей вершин орграфа может оказаться симметричной относительно главной диагонали лишь в редких частных случаях.
Как и в случае неориентированных графов, каждый орграф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная матрица, элементы которой - целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма ориентированный граф.
Определение 3. Матрицей инцидентности неориентированного графа G называется матрица B(G)=bij размером (p x q) (p и q - количество вершин и ребер графа), элементы bij которой равны единице, если вершина xi инцидентна ребру ej и нулю, если соответствующие вершины и ребра не инцидентны.
Свойства матрицы инцидентности неориентированного графа.
1. Сумма элементов матрицы на i-й строке равна (xi).
2. Сумма элементов матрицы по i-му столбцы равна 2.
Матрица инцидентности графа, изображенного на рис. 1, а имеет вид:
e1
E2
e3
e4
e5
e6
e7
e8
e9
e10
x1
1
1
2
0
0
0
0
0
0
0
x2
0
0
0
1
1
1
0
0
0
0
x3
0
0
0
0
0
1
1
1
0
0
B(G)
=
x4
0
0
0
0
0
0
0
1
1
0
x5
1
0
0
0
0
0
0
0
1
1
x6
0
0
0
0
1
0
1
0
0
0
x7
0
1
0
1
0
0
0
0
0
0
x8
0
0
0
0
0
0
0
0
0
1
Следует отметить, что петле ej=(xi, xi) в матрицах этого вида соответствует j-й столбец, состоящий из нулей и одной единицы, расположенной на i-м месте. Ребру ek=xm, xn соответствует в матрице инциденций k-й столбец, состоящий из нулей и двух и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.