Графы. Основные понятия

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

Рубрика Математика
Вид лабораторная работа
Язык русский
Дата добавления 09.01.2009
Размер файла 85,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Министерство образования и науки Российской Федерации

Курский государственный технический университет

Кафедра ПО ВТ и АС

Лабораторная работа № 1

Графы. Основные понятия

Выполнил: студент гр. ПО 62 Шиляков И.А.

Проверил: доцентТомакова Р.А.

Курск 2007

Задание:

1. По заданным матрицам смежности вершин восстановить графы.

2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.

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

4. Найти композицию графов .

5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.

7. Определить хроматические и цикломатические числа данных графов.

8. Найти все базы графа.

9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Выполнение:

1. По заданным матрицам смежности вершин восстановить графы.

x1

x2

x3

x4

x5

x6

x7

x1

0

1

0

0

0

0

1

x2

0

0

1

0

0

1

0

x3

0

1

0

1

0

0

0

x4

1

0

0

0

1

0

0

x5

1

0

0

0

0

0

1

x6

0

0

1

1

0

0

0

x7

0

0

0

0

1

1

0

A1

G1(X1,A1)

x1

x2

x3

x4

x5

x6

x7

x1

0

1

1

0

0

0

0

x2

0

0

0

1

1

0

0

x3

0

1

0

0

0

0

1

x4

1

0

0

0

1

0

0

x5

0

0

0

0

0

1

1

x6

1

0

0

1

0

0

0

x7

0

0

1

0

0

1

0

A2

G2(X2,A2)

2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а1

0

1

1

1

1

0

1

0

1

0

0

0

0

0

а2

1

0

0

0

0

0

1

0

1

1

0

0

1

1

а3

1

0

0

1

1

1

0

0

0

0

1

0

0

0

а4

1

0

1

0

1

0

0

0

0

0

1

1

0

1

а5

1

0

1

1

0

1

0

0

0

0

1

0

0

0

а6

0

0

1

0

1

0

1

1

0

0

1

1

0

0

а7

1

1

0

0

0

1

0

1

1

0

0

1

0

0

а8

0

0

0

0

0

1

1

0

1

1

0

1

1

0

а9

1

1

0

0

0

0

1

1

0

1

0

0

1

0

а10

0

1

0

0

0

0

0

1

1

0

0

0

1

1

а11

0

0

1

1

1

1

0

0

0

0

0

1

0

1

а12

0

0

0

1

0

1

1

1

0

0

1

0

0

1

а13

0

1

0

0

0

0

0

1

1

1

0

0

0

1

а14

0

1

0

1

0

0

0

0

0

1

1

1

1

0

B1

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а1

0

1

0

1

1

1

1

0

1

0

0

0

0

0

а2

1

0

1

1

1

1

0

1

0

0

0

0

0

0

а3

0

1

0

1

0

0

1

1

0

0

0

1

1

0

а4

1

1

1

0

0

0

1

1

1

0

0

0

0

0

а5

1

1

0

0

0

1

0

0

0

1

1

0

0

0

а6

1

1

0

0

1

0

0

0

0

1

1

0

0

0

а7

1

0

1

1

0

0

0

0

1

0

0

1

1

0

а8

0

1

1

1

0

0

0

0

0

0

1

0

1

1

а9

1

0

0

1

0

0

1

0

0

1

0

1

0

1

а10

0

0

0

0

1

1

0

0

1

0

1

1

0

1

а11

0

0

0

0

1

1

0

1

0

1

0

0

1

1

а12

0

0

1

0

0

0

1

0

1

1

0

0

1

1

а13

0

0

1

0

0

0

1

1

0

0

1

1

0

1

а14

0

0

0

0

0

0

0

1

1

1

1

1

1

0

B2

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

x1

1

1

0

0

0

0

-1

0

-1

0

0

0

0

0

x2

-1

0

1

1

-1

0

0

0

0

0

0

0

0

0

x3

0

0

-1

0

1

1

0

0

0

0

-1

0

0

0

x4

0

0

0

0

0

-1

1

1

0

0

0

-1

0

0

x5

0

0

0

0

0

0

0

-1

1

1

0

0

-1

0

x6

0

0

0

-1

0

0

0

0

0

0

1

1

0

-1

x7

0

-1

0

0

0

0

0

0

0

-1

0

0

1

1

S1

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

x1

1

0

0

1

0

0

-1

0

-1

0

0

0

0

0

x2

0

-1

1

-1

0

0

0

1

0

0

0

0

0

0

x3

-1

1

0

0

-1

1

0

0

0

0

0

0

0

0

x4

0

0

-1

0

0

0

1

0

0

0

0

-1

1

0

x5

0

0

0

0

0

0

0

-1

0

0

1

0

-1

1

x6

0

0

0

0

0

0

0

0

1

-1

0

1

0

-1

x7

0

0

0

0

1

-1

0

0

0

1

-1

0

0

0

S2

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1

R1 R2

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1

Q1 Q2

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

Объединение графов

G3(X3,A3)=G1(X1,A1) YG2(X2,A2); X3= X1YX2, A3= A1YA2

Пересечение графов

G3(X3,A3)=G1(X1,A1) ?G2(X2,A2); X3= X1?X2, A3= A1?A2

Кольцевая сумма графов

G3(X3,A3)=G1(X1,A1)G2(X2,A2)

4. Найти и построить композицию графов .

G1(Х)

G2(Х)

G1(G2(Х))

G2(G1(Х))

x1

(x1,x2), (x1,x7)

(x1,x2), (x1,x3)

(x1,x3), (x1,x6),

(x1,x2), (x1,x4),

(x1,x4), (x1,x5),

(x1,x3), (x1,x6),

x2

(x2,x3),

(x2,x6)

(x2,x4),

(x2,x5)

(x2,x1), (x2,x5),

(x2,x7),

(x2,x2), (x2,x7),

(x2,x1), (x2,x4),

x3

(x3,x2),

(x3,x4)

(x3,x2),

(x3,x7)

(x3,x3), (x3,x6),

(x3,x5),

(x3,x4), (x3,x5),

(x3,x1),

x4

(x4,x1), (x4,x5)

(x4,x1), (x4,x5)

(x4,x2), (x4,x7),

(x4,x1),

(x4,x2), (x4,x3),

(x4,x6), (x4,x7),

x5

(x5,x1), (x5,x7)

(x5,x6), (x5,x7)

(x5,x3), (x5,x4),

(x5,x5), (x5,x6),

(x5,x2), (x5,x3),

(x5,x6),

x6

(x6,x3),

(x6,x4)

(x6,x1),

(x6,x4)

(x6,x2), (x6,x7),

(x6,x1), (x6,x5),

(x6,x2), (x6,x7),

(x6,x1), (x6,x5),

x7

(x7,x5), (x7,x6)

(x7,x3), (x7,x6)

(x7,x2), (x7,x4),

(x7,x3),

(x7,x6), (x7,x7),

(x7,x1), (x7,x4),

G1(G2(Х))

G2(G1(Х))

5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

Остовные подграфы

G'1(X1,A1)

G'2(X2,A2)

Произвольные подграфы

G1'' (X1'',A1'')

G2'' (X2'',A2'')

Порожденные подграфы

G1P(X1P,A1P) G2P(X2P,A2P)

6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.

Локальные степени графа G1

11)=2 ; 21)=2 ; (х1)=4 ;

12)=2 ; 22)=2 ; (х2)=4 ;

13)=2 ; 23)=2 ; (х3)=4 ;

14)=2 ; 24)=2 ; (х4)=4 ;

15)=2 ; 25)=2 ; (х5)=4 ;

16)=2 ; 26)=2 ; (х6)=4 ;

17)=2 ; 27)=2 ; (х7)=4 ;

Локальные степени графа G2

11)=2 ; 21)=2 ; (х1)=4 ;

12)=2 ; 22)=2 ; (х2)=4 ;

13)=3 ; 23)=2 ; (х3)=4 ;

14)=2 ; 24)=2 ; (х4)=4 ;

15)=2 ; 25)=2 ; (х5)=4 ;

16)=2 ; 26)=2 ; (х6)=4 ;

17)=2 ; 27)=2 ; (х7)=4 ;

Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны.

Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны.

7. Определить хроматические и цикломатические числа данных графов.

Хроматическое число г для графа G1 = 4

Хроматическое число г для графа G2 = 4

Цикломатические числа графов

V(G1)=m-n+r, где m - число рёбер (дуг);

n - число вершин;

r - число компонент связности.

V(G1)=14-7+1=8;

V(G2)=14-7+1=8;

8. Найти все базы графа.

Базы графа G1

B1={x1}

B2={x2}

B3={x3}

B4={x4}

B5={x5}

B6={x6}

B7={x7}

Базы графа G2

B1={x1}

B2={x2}

B3={x3}

B4={x4}

B5={x5}

B6={x6}

B7={x7}

9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Сильные компоненты связности G1

СК={x1, x2, x3, x4, x5, x6, x7}

Сильные компоненты связности G2

СК={x1, x2, x3, x4, x5, x6, x7}

Конденсация графа G1 Конденсация графа G2


Подобные документы

  • Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.

    курсовая работа [625,4 K], добавлен 30.09.2014

  • Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.

    курсовая работа [225,5 K], добавлен 14.05.2012

  • История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.

    курсовая работа [636,2 K], добавлен 20.12.2015

  • Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.

    контрольная работа [463,0 K], добавлен 17.05.2015

  • Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.

    лабораторная работа [42,2 K], добавлен 11.03.2012

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

    курсовая работа [423,7 K], добавлен 21.02.2009

  • Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.

    презентация [150,3 K], добавлен 16.01.2015

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

    реферат [81,0 K], добавлен 23.11.2008

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

    курсовая работа [271,1 K], добавлен 09.05.2015

  • Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.

    реферат [368,2 K], добавлен 13.06.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.