Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности



Скачать 160.65 Kb.
Дата04.07.2013
Размер160.65 Kb.
ТипДокументы
Министерство образования и науки РФ

Алтайский государственный технический университет им.И.И. Ползунова
Институт интенсивного образования

Каменское представительство
К О Н Т Р О Л Ь Н А Я Р А Б О Т А

по дисциплине «Графы и автоматы»
Выполнил: студент гр.Км(з) ПИЭ-71

Ковалева Т.В.

Проверил: к.ф.-м.н. доцент

Бразовская О.В.


г. Камень-на-Оби

2009

  1. Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности.


Графом G называется совокупность двух множеств: вершин V и рёбер E, между элементами которых определено отношение инцидентности (т.е. каждое ребро еЕ инцидентно ровно двум вершинам v и v’’V, которые оно соединяет).

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

Построим неориентированный граф:







а b c





d

k

e










m




f


  1. Матрицы смежности и инцидентности.


Матрица смежности – это квадратная матрица размера nn: по вертикали и горизонтали перечисляются все вершины vj V, а на пересечении k-той и i-той вершин проставляется число, равное числу рёбер, соединяющих эти вершины.


Построим матрицу смежности:





1

2

3

4

5

6

7

1

0

1

0

0

0

0

0

2

1

0

1

0

0

1

0

3

0

1

0

1

1

0

0

4

0

0

1

0

1

0

0

5

0

0

1

1

0

1

0

6

0

1

0

0

1

0

1

7

0

0

0

0

0

1

0


Матрица инцидентности – это матрица размера nn: по вертикали и горизонтали указываются вершины и рёбра соответственно, а на пересечении i-той вершины и j-того ребра в случае неориентированного графа проставляется 1, если они инцидентны, и 0 – в противном случае.

Отношение инцидентности – каждое ребро инцидентно ровно двум вершинам, которые оно соединяет.

Построим матрицу инцидентности:





a

b

c

d

e

f

k

m

1

1

0

0

0

0

0

0

0

2

1

1

0

0

0

0

1

0

3

0

1

1

0

1

0

0

0

4

0

0

1

1

0

0

0

0

5

0

0

0

1

1

1

0

0

6

0

0

0

0

0

1

1

1

7

0

0

0

0

0

0

0

1



  1. Задать функции разметки.


- множество меток вершин, - множество меток ребер,

- разметка вершин, - разметка ребер.

- размечен и , - размечен и ;

- без разметки & ,

,

.

& - разметка вершин;

& - разметка ребер.





1

2

3

4

5

6

7

1

0

a

0

0

0

0

0

2

a

0

b

0

0

k

0

3

0

b

0

c

e

0

0

4

0

0

c

0

d

0

0

5

0

0

e

d

0

f

0

6

0

k

0

0

f

0

m

7

0

0

0

0

0

m

0



  1. Построить подграф, являющийся остовным деревом.


Подграфом G(V) графа G(V) называется часть, которой принадлежат все рёбра с обоими концами из V.

  • - дерево - связный ациклический. Остовное дерево – остовной подграф & дерево.

Т.: , - матрица смежности; , - число маршрутов из в длины .

Построим 2 подграфа:




c a

b



d k
e




m


  1. Определить число маршрутов длины 5 между каждой парой вершин.




из 1 в 1 – нет

из 1 в 2 – нет

из 1 в 3 – да

(a, k, f, d, c)

из 1 в 4 – да

(a, k, f, e, c)

из 1 в 5 – нет

из 1 в 6 – да

(a, b, c, d, f)

из 1 в 7 – да

(a, b, e, f, m)


из 2 в 1 – нет

из 2 в 2 – да

(k, f, d, c, b)

(b, c, d, f, k)

из 2 в 3 – нет

из 2 в 4 – нет

из 2 в 5 – нет

из 2 в 6 – нет

из 2 в 7 – да

(b, c, d, f, m)

из 3 в 1 – да

(c, d, f, k, a)

из 3 в 2 – нет

из 3 в 3 – да

(c, d, f, k, b)

(b, k, f, d, c)

из 3 в 4 – нет

из 3 в 5 – нет

из 3 в 6 – нет

из 3 в 7 - нет

из 4 в 1 – да

(c, e, f, k, a)

из 4 в 2 – нет

из 4 в 3 – нет

из 4 в 4 – да

(d, f, k, b, c)

(c, b, k, f, d)

из 4 в 5 – нет

из 4 в 6 – нет

из 4 в 7 – да

(d, e, b, k, m)


из 5 в 1 – нет

из 5 в 2 – нет

из 5 в 3 – нет

из 5 в 4 – нет

из 5 в 5 – да

(d, c, b, k, f)

(f, k, b, c, d)

из 5 в 6 – нет

из 5 в 7 – да

(d, c, b, k, m)

из 6 в 1 – да

(f, d, c, b, a)

из 6 в 2 – нет

из 6 в 3 – нет

из 6 в 4 – нет

из 6 в 5 – нет

из 6 в 6 – да

(f, d, c, b, k)

(k, b, c, d, f)

из 6 в 7 - нет

из 7 в 1 – да

(m, f, e, b, a)

из 7 в 2 – да

(m, f, d, c, b)

из 7 в 3 – нет

из 7 в 4 – да

(m, k, b, e, d)

из 7 в 5 – да

(m, k, b, c, d)

из 7 в 6 – нет

из 7 в 7 - нет





Итого длиною в 5 – 24 маршрута


  1. Построить матрицу связности вершин.


Количество маршрутов (любой длины между i-той и j-той вершинами.





1

2

3

4

5

6

7

1

0

1

3

4

3

3

3

2

1

4

3

4

3

3

3

3

3

3

6

3

3

3

3

4

3

3

3

4

3

3

4

5

3

3

3

3

6

3

3

6

3

3

3

3

3

4

1

7

3

3

3

3

3

1

0




  1. Изобразить карту графа или убедиться, что её не существует.


Карта графа строится на основе числа маршрутов между каждой парой вершин.

  • - планарный, если он плоский (нет пересечений на ).

Карта – изображение планарного графа, , - число областей карты.

1 3




3



3

3







1 3


  1. Получить матрицы списков смежности вершин.







1

2

3

4

5

6

7

1

-

+

-

-

-

-

-

2

+

-

+

-

-

+

-

3

-

+

-

+

+

-

-

4

-

-

+

-

+

-

-

5

-

-

+

+

-

+

-

6

-

+

-

-

+

-

+

7

-

-

-

-

-

+

-




  1. Осуществить обход по ширине и глубине графа.

Обход по ширине: Пара вершин, между которыми существует наибольшее количество маршрутов разной длины.
Самое большое количество маршрутов равно 6-ти, это между вершиной 3 и 3, и вершиной 5. Например, из вершины 3 в вершину 3 можно пройти следующими способами:

  1. c, d, e

  2. e, d, c

  3. b, k, f, e

  4. e, f, k, b

  5. b, k, f, d, c

  6. c, d, f, k, b


и вершиной 5:

  1. e, c, d

  2. d, c, e

  3. f, k, b, e

  4. e, b, k, f

  5. f, k, b, c, d

  6. d, c, b, k, f


Обход по глубине: Самый длинный маршрут.
Самый длинный маршрут из вершины 1 в вершину 7, он равен 6:

a, b, c, d, f, m



  1. Преобразовать граф в ориентированный и найти матрицу отношения связности на нём.


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

Граф, содержащий направленные рёбра, называется ориентированный.

Преобразуем граф в ориентированный.























Построим матрицу отношений связности для ориентированного графа.





1

2

3

4

5

6

7

1

0

1

0

0

0

0

0

2

0

0

0

0

0

0

0

3

0

1

1

1

1

1

0

4

0

2

1

1

1

1

0

5

0

2

1

1

1

1

0

6

0

1

0

0

0

0

0

7

0

1

0

0

0

1

0

Похожие:

Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconДать определения понятиям
Построить модель сети в виде графа. Задать нумерацию вершин с Задать граф в виде матрицы смежности. Задать граф в виде списка ребер...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconРасчетно-графическая работа
Граф называется автоморфным, если существует такая перестановка вершин, которая сохранила бы отношения смежности. Другими словами,...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconБиблиотека "g-lib" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа
В библиотеке реализованы четыре основных способа задания графа: список ребер, матрица смежности, список инцидентности вершин входящих...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconДискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах
Понятие неориентированного графа. Способы задания графа. Матрицы смежности. Путь в графе. Цикл в графе. Связный граф. Компоненты...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconУдк 681 001. 63 Эволюционные процедуры решения комбинаторных задач на графах
...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconЗадача Нарисуйте граф с множеством вершин и множеством рёбер Выпишите его матрицу смежности

Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности icon1. Основные понятия и определения
Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром, если упорядочена – дугой. Граф, состоящий только из...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconРебром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным
Граф, содержащий только дуги, – ориентированным. Пара вершин может соединяться двумя или более ребрами (дугами одного направления),...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Изобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности iconВариант Вычислить весы ребер. Вывести матрицу смежности взвешенного неориентированного графа. Построить остовное связное дерево минимального веса. Даны координаты вершин графа. А 46 51 51 83 43 53 6 60 17 96 б 48 37 86 62 40 3 31 40 99 70
Вычислить весы ребер. Вывести матрицу смежности взвешенного неориентированного графа. Построить остовное связное дерево минимального...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org