«Расчет числовых характеристик графов»



страница1/2
Дата04.07.2013
Размер0.59 Mb.
ТипДокументы
  1   2


Федеральное агентство по образованию

Балтийский федеральный университет им. И. Канта

Институт современных образовательных технологий

Кафедра компьютерного моделирования и информационных систем

Расчетно-графическая работа №6

по дисциплине

«Теоретические основы информатики»

по теме

«Расчет числовых характеристик графов»

(вариант 10)

Выполнил:

студент 3 курса очного отделения

направления «физико-математическое образование»,

профиля «информатика»

Павлов Сергей

Проверил:

доктор технических наук,

профессор А.В. Колесников

Калининград 2012

Содержание

  1. Расчет числовых характеристик графа

    1. Расчет количества вершин n (G) графа G……………………………. ..3

    2. Расчет количества ребер m (G) графа G ……………………………... ..3

    3. Расчет степеней вершин δi графа G……………………………………..3

    4. Расчет числа компонент связности æ(G)……………………………….4

    5. Расчет цикломатического числа λ(G) графа G…………………………8

    6. Расчет хроматического числа γ(G) графа G…………………………….8

    7. Расчет плотности (G) графа G………………………………………..12

    8. Расчет неплотности ε(G) графа G………………………………............13

    9. Расчет внешней устойчивости ψ(G) графа G………………………….15

    10. Расчет числа внутренней устойчивости (G) графа G……………...17

Список использованной литературы………………………………………….19

Вариант 10.

  1. Расчет числовых характеристик графа

Пусть задан граф G.



Рисунок 1.1 Граф G

    1. Расчет количества вершин n (G) графа G

Расчет выполняется методом визуального анализа графа G.

n (G) = 11

1.2 Расчет количества ребер m(G) графа G

Расчет выполняется методом визуального анализа графа G.

m (G) = 15

1.
3 Расчет степеней вершин δi графа G


Расчет выполняется методом визуального анализа графа G с целью определения количества ребер (дуг) инцидентных вершине xi. Результаты расчета представлены в таблице 1.1.

Таблица 1.1 – Результаты расчета степеней вершин графа G

xi

δi

1

2

2

2

3

2

4

2

5

4

6

3

7

2

8

5

9

2

10

3

11

3

1.4 Расчет числа компонент связности æ(G)

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





где ||1|| — единичная матрица,

||H(xi)|| — матрица смежности графа G,

||Hp(xi)|| — матрица смежности графа G, возведенная в p—ую степень

1

1

2

3

4

5

6

7

8

9

10

11

1

1

0

0

0

0

0

0

0

0

0

0

2

0

1

0

0

0

0

0

0

0

0

0

3

0

0

1

0

0

0

0

0

0

0

0

4

0

0

0

1

0

0

0

0

0

0

0

5

0

0

0

0

1

0

0

0

0

0

0

6

0

0

0

0

0

1

0

0

0

0

0

7

0

0

0

0

0

0

1

0

0

0

0

8

0

0

0

0

0

0

0

1

0

0

0

9

0

0

0

0

0

0

0

0

1

0

0

10

0

0

0

0

0

0

0

0

0

1

0

11

0

0

0

0

0

0

0

0

0

0

1

Рисунок 1.2 Единичная матрица для графа G

Построим матрицу смежности для графа G.

H

1

2

3

4

5

6

7

8

9

10

11

1

0

1

1

0

0

0

0

0

0

0

0

2

1

0

1

0

0

0

0

0

0

0

0

3

1

1

0

0

0

0

0

0

0

0

0

4

0

0

0

0

1

0

0

0

0

1

0

5

0

0

0

1

0

1

0

1

0

1

0

6

0

0

0

0

1

0

1

1

0

0

0

7

0

0

0

0

0

1

0

1

0

0

0

8

0

0

0

0

0

1

1

0

1

0

1

9

0

0

0

0

0

0

0

1

0

0

1

10

0

0

0

1

1

0

0

0

0

0

1

11

0

0

0

0

0

0

0

1

1

1

0

Рисунок 1.3 — Матрица смежности ||H|| графа G

Получим матрицу достижимости ||Q|| графа G (рисунок 1.4).

Q

1

2

3

4

5

6

7

8

9

10

11

1

1

1

1

0

0

0

0

0

0

0

0

2

1

1

1

0

0

0

0

0

0

0

0

3

1

1

1

0

0

0

0

0

0

0

0

4

0

0

0

1

1

0

0

0

0

1

0

5

0

0

0

1

1

1

0

1

0

1

0

6

0

0

0

0

1

1

1

1

0

0

0

7

0

0

0

0

0

1

1

1

0

0

0

8

0

0

0

0

0

1

1

1

1

0

1

9

0

0

0

0

0

0

0

1

1

0

1

10

0

0

0

1

1

0

0

0

0

1

1

011

0

0

0

0

0

0

0

1

1

1

1

Рисунок 1.4 — Матрица достижимости ||Q|| графа G

Возведем матрицу смежности ||H|| в квадрат, получим ||H2|| (рисунок 1.5)

H2

1

2

3

4

5

6

7

8

9

10

11

1

1

1

1

0

0

0

0

0

0

0

0

2

1

1

1

0

0

0

0

0

0

0

0

3

1

1

1

0

0

0

0

0

0

0

0

4

0

0

0

1

1

1

0

1

0

1

1

5

0

0

0

1

1

1

1

1

1

1

1

6

0

0

0

1

0

1

1

1

1

1

1

7

0

0

0

0

1

1

1

1

1

0

1

8

0

0

0

0

1

1

1

1

1

1

1

9

0

0

0

0

0

1

1

1

1

1

1

10

0

0

0

1

1

1

0

1

1

1

0

11

0

0

0

1

1

1

1

1

1

0

1

Рисунок 1.5 - Матрица ||H2|| графа G

Возведем матрицу смежности ||H|| в третью степень. Получим ||H3|| (рисунок 1.6).

H3

1

2

3

4

5

6

7

8

9

10

11

1

1

1

1

0

0

0

0

0

0

0

0

2

1

1

1

0

0

0

0

0

0

0

0

3

1

1

1

0

0

0

0

0

0

0

0

4

0

0

0

1

1

1

1

1

1

1

1

5

0

0

0

1

1

1

1

1

1

1

1

6

0

0

0

1

1

1

1

1

1

1

1

7

0

0

0

1

1

1

1

1

1

1

1

8

0

0

0

1

1

1

1

1

1

1

1

9

0

0

0

1

1

1

1

1

1

1

1

10

0

0

0

1

1

1

1

1

1

1

1

11

0

0

0

1

1

1

1

1

1

1

1

Рисунок 1.5 - Матрица ||H3|| графа G

Анализ матриц ||H2|| и ||H3|| показывает, что никаких изменений в ||H3|| по сравнению ||H2|| нет. Значит процесс вычислений завершен.

Матрица достижимости ||Q3|| (рис. 5.9) рассчитывается следующим образом:

Q3

1

2

3

4

5

6

7

8

9

10

11

1

1

1

1

0

0

0

0

0

0

0

0

2

1

1

1

0

0

0

0

0

0

0

0

3

1

1

1

0

0

0

0

0

0

0

0

4

0

0

0

1

1

1

1

1

1

1

1

5

0

0

0

1

1

1

1

1

1

1

1

6

0

0

0

1

1

1

1

1

1

1

1

7

0

0

0

1

1

1

1

1

1

1

1

8

0

0

0

1

1

1

1

1

1

1

1

9

0

0

0

1

1

1

1

1

1

1

1

10

0

0

0

1

1

1

1

1

1

1

1

11

0

0

0

1

1

1

1

1

1

1

1

Рисунок 1.8— Матрица ||Q5|| графа G

Поскольку матрица ||Q3|| содержит два блока: один — 3х3 элемента, другой — 6х6 элементов, то граф G содержит два связных подграфа:


G1 = <X1, H1>, G2 = <X2, H2>,


где X1={x1,x2,x3}, X2={x4,x5,x6,x7,x8,x9}.

Таким образом, для исходного графа G = <X,H> число компонент связности равно æ(G)=2.
  1   2

Похожие:

«Расчет числовых характеристик графов» iconРешение Усилительное (пропорциональное, идеальное, безынерционное звено). Вывод передаточной функции
Ачх), фазочастотных (фчх) и амплитудно-фазовых (афх) характеристик. Рассчитать и построить графики переходных функций и частотных...
«Расчет числовых характеристик графов» iconМатематические методы в психологии
Описательная статистика: вычисление числовых характеристик распределения признака
«Расчет числовых характеристик графов» iconРасчет показателей вариации в ms excel
Число1, число2, это от 1 до 30 числовых аргументов, соответствующих выборке из генеральной совокупности
«Расчет числовых характеристик графов» iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
«Расчет числовых характеристик графов» iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
«Расчет числовых характеристик графов» iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
«Расчет числовых характеристик графов» iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
«Расчет числовых характеристик графов» iconЛекции №6 Основные свойства числовых характеристик 1 Теоремы о математических ожиданиях
Доказательство. Мы можем рассматривать постоянную величину как предельный случай случайной величины, которая принимает единственное...
«Расчет числовых характеристик графов» iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
«Расчет числовых характеристик графов» iconУдк 621. 74. Авторы
Расчет статических характеристик пузырей и их изменения по глубине тигля при пузырьковой дегазации металла
Разместите кнопку на своём сайте:
ru.convdocs.org


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