35546

Исследование свойств графов. Построение основных матриц. Решение системы линейных алгебраических уравнений методом графов

Практическая работа

Математика и математический анализ

Исключив общее ребро е из двух несовпадающих циклов, мы превратим эти циклы в две несовпадающие простые цепи, объединение которых, в силу свойств цепей, будет содержать простой цикл (естественно, без ребра е).

Русский

2013-09-16

306 KB

20 чел.

РГЗ №1 «Исследование свойств графов. Построение основных матриц. Решение системы линейных алгебраических уравнений методом графов».

ВАРИАНТ 16.

ЗАДАЧА 1.

Показать, что если два различных цикла графа содержат ребро e, то в графе существует цикл, не содержащий е.

РЕШЕНИЕ:

Исключив общее ребро е из двух несовпадающих циклов, мы превратим эти циклы в две несовпадающие простые цепи, объединение которых, в силу свойств цепей, будет содержать простой цикл (естественно, без ребра е).  

ЗАДАЧА 2.

 По заданному орграфу построить матрицы:

  •  инцидентности;
  •  БРМ;
  •  БЦ;
  •  смежности.

РЕШЕНИЕ:

Хочу отметить, что в условии задачи неправильно пронумерованы ребра орграфа – всего в графе 8 ребер, но их нумерация на рисунке заканчивается не 8-м номером, а 9-м. В связи с этим будем считать, что орграф на самом деле такой:

 

а) Матрица инцидентности орграфа:

1

2

3

4

5

6

7

8

-1

1

1

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

-1

0

-1

0

0

0

0

0

0

-1

0

0

-1

-1

0

-1

0

0

0

-1

0

1

1

0

0

1

1

0

0

0

б) Легко увидеть, что остовом D данного графа является:

Отметим, что хордами для данного остова D будут являться ребра 1,4,8.

Для нахождения базисного разрезающего множества найдем разрезы графа G. Для этого удалим ребро остова D. Множество вершин при этом распадается на два непересекающихся подмножества  и . Множество всех ребер в , каждое из которых соединяет вершину из  с вершиной из , является разрезом графа . Множество разрезов графа G образуют базисное разрезающее множество графа G, которое можно записать в виде матрицы.

Базисная система разрезов для графа  и остовного дерева  состоит из разрезов:  . Запишем матрицу БРМ:

2

3

5

6

7

1

4

8

K1

1

0

0

0

0

0

1

0

K2

0

1

0

0

0

1

1

0

K3

0

0

0

1

0

0

1

1

K4

0

0

0

0

1

0

1

1

K5

0

0

1

0

0

1

1

0

в) Базисной системой циклов для данного остова  графа  называется множество всех циклов графа , каждый из которых содержит только одну хорду . Эта система образует базис пространства циклов. В нашем графе циклы R1 ={1,3,5}, R2={2,3,4,5,6,7}, R3={4,6,7} являются базисными, соответственно матрица БЦ относительно остова D имеет вид:

1

4

8

2

3

5

6

7

1

0

0

0

1

1

0

0

R1

0

1

0

1

1

1

1

1

R2

0

0

1

0

0

0

1

1

R3

  

г) Матрица смежности орграфа:

0

0

1

0

1

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

0

1

1

0

0

ЗАДАЧА 3.

Решить систему методом Коутса:

          если n - четно

где:

n - номер варианта;=16

k - дата (день) рождения,=20

m - месяц (его номер) рождения студента.=10

С учетом моих данных имеем систему:

  или

РЕШЕНИЕ:

Наша система уравнений в матричном виде имеет вид:

Матрица  , которая  получается добавлением –B к правой части матрицы A и затем нулевой строки к нижней части получившейся матрицы, имеет вид:

Транспонированная матрица будет матрицей смежности графа Коутса, соответствующего нашей системе уравнений:

 

Построим по полученной матрице смежности граф Коутса :

 

Граф Коутса для исходной матрицы A имеет вид:

Решение уравнения определим по формуле:

, где - 1-факториальное соединение вершины с вершиной в графе ; H – 1-фактор графа ;  и  - число циклов в  и соответственно.

Приведем 1- факторы графа  со своими весовыми произведениями:

1-фактор

Весовое произведение

-1120

-512

Значит:

Пользуясь изложенной формулой найдем, например, соотношение .

Приведем 1-факториальные соединения с (в скобки заключаются также вершины, лежащие в ориентированном пути):

1-факториальное соединение

Весовое произведение

320

896

Значит:

Получаем, что :

Аналогично приведем 1-факториальные соединения с :

1-факториальное соединение

Весовое произведение

128

784

Значит:

Получаем, что :

1-факториальные соединения с :

1-факториальное соединение

Весовое произведение

960

-1680

-1960

-320

2688

-768

Значит:

Получаем, что: .

Ответ: ,  - свободная переменная.

  Заданная система уравнений имеет множество решений.


-4

7

6

5

3

2

8

7

6

5

4

3

2

1

EMBED Equation.3  

-6

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  

8

9

7

6

5

4

3

2

1

-14

-4

14

EMBED Equation.3  

EMBED Equation.3  

-4

20

14

EMBED Equation.3  

16

-12

EMBED Equation.3  

10

8

16

-12

EMBED Equation.3  

10

8

20

EMBED Equation.3  


 

А также другие работы, которые могут Вас заинтересовать

18052. Основы радиации. Радиационное загрязнение территории РБ 599 KB
  1. Радиационное загрязнение территории РБ. Радиоактивность явл результатом процесса кот происх внутри ядер. НТР принесла чел не только технический прогресс но и истощение природных ресурсов загрязнение окр среды усиление техногенной экологической и природной опас
18053. Административно-процессуальное право: Курс лекций 1.11 MB
  Административно-процессуальное право: Курс лекций./ Сост.: В.В. Степанюк Орёл: Орловский юридический институт МВД России 2009 г. 172 с. В данном курсе лекций представлены конспекты лекций по первому разделу: Введение в административнопроцессуал
18054. ТИПИЧНЫЕ ОШИБКИ ПРИ НАЧИСЛЕНИИ НАЛОГОВ И СТРАХОВЫХ ВЗНОСОВ 2.87 MB
  ТИПИЧНЫЕ ОШИБКИ ПРИ НАЧИСЛЕНИИ НАЛОГОВ И СТРАХОВЫХ ВЗНОСОВ Ф.Н. Филина И.А. Толмачев Под редакцией Т.Н. Межуевой. НАЛОГ НА ПРИБЫЛЬ 1.1. Доходы В соответствии со ст. 41 Налогового кодекса РФ доходом признается экономическая выгода в денежной или натурал...
18055. Анализ деятельности коммерческого банка 1.36 MB
  Л.В. КОХ Ю.В. КОХ Анализ деятельности коммерческого банка Учебное пособие Раскрываются основные направления экономического анализа деятельности коммерческого банка. Рассматриваются вопросы анализа состояния и использования собственных и привлеченных средств...
18056. Організація, планування та управління підприємствами галузі: Конспект лекцій 1.35 MB
  Стахурський В.О. Організація планування та управління підприємствами галузі: Конспект лекцій для студ. напрямів 0902 Інженерна механіка 0905 Енергетика 0925 Автоматизація та компютерно-інтегровані технології всіх форм навчання. – К. : НУХТ 2009. – 113 с. АНОТАЦІЯ К
18057. Базы данных, учебное пособие 1.41 MB
  Базы данных Допущено Учебно-методическим объединением вузов по образованию в области автоматизированного машиностроения УМО АМ в качестве учебного пособия для студентов высших учебных заведений обучающихся по направлениям подготовки бакалавров и магистров.
18058. Проблемы подростковой адаптации с позиций профилактики и психотерапии личностных и поведенческих расстройств и зависимости от психоактивных веществ 1.06 MB
  Проблемы подростковой адаптации с позиций профилактики и психотерапии личностных и поведенческих расстройств и зависимости от психоактивных веществ М. 325 с. Вместо введения. История создания книги Психическая адаптация к требованиям социальной среды. Базисные ком...
18059. Практикум по арбитражному процессу 1.2 MB
  Практикум по арбитражному процессу Учебное пособие для студентов юридических вузов и факультетов Под редакцией доктора юридических наук профессора В. В. Яркова и кандидата юридических наук доцента С.Л. Дегтярева 2е издание переработанное и дополненное .: ...
18060. ИСТОРИЯ ДЕНЕЖНО-КРЕДИТНОЙ СИСТЕМЫ РОССИИ 1.53 MB
  История денежнокредитной системы России В пособии раскрывается процесс зарождения и формирования денежной системы возникновение банковского дела становления и развития банковской системы России. В первой части излагается процесс формирования и развития денежной с...