35546

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

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

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

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

Русский

2013-09-16

306 KB

21 чел.

РГЗ №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  


 

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

46439. Получение счетов на оплату товаров – заключительный этап выполнения договора 15.77 KB
  Форма расчетов: если иное не предусмотрено договором расчеты должны осуществляться платежными поручениямибанковский перевод Срок оплаты: если в договоре не указан срок оплаты и не предусмотрена предварительная оплата то платеж должен быть совершен сразу после получения товара. Безналичные расчеты между субъектами хозяйствования: Расчеты платежными поручениями. Расчеты по аккредитиву. Расчеты по инкассо Расчеты чеками .
46440. Ремонт деталей класса «Валы». Восстановление шлицевых и шпоночных пазов 15.79 KB
  В процессе эксплуатации у валов и осей изнашиваются посадочные шейки шпоночные канавки и шлицы повреждаются резьбы поверхности валов центрирующие отверстия а также происходит изгиб валов. Характерные дефекты валов: 1 износ повти трения в опорах; 2 износ сопрягаемых повтей с подшипниками качения; 3 разруше или смятие шпоночных пазов; 4 изгиб оси вала; 5 повреждение или износ резьбовых соединений; 6 продольный изгиб вала. Особое внимание при дефектовке уделяют контролю коленчатых валов. Шейки валов имеющие царапины риски и...
46442. Классификация объектов интеллектуальной собственности 15.81 KB
  К объектам промышленной собственности относятся: изобретения; промышленные образцы; полезные модели; товарные знаки; знаки обслуживания; наименование мест происхождения товара. Сделка может заключаться как по одному так и по нескольким патентам на изобретения. Беспатентными являются изобретения на которые поданы патентные заявки но не получены патенты на изобретения; изобретения не патентуемые изобретателями в целях сохранения секретности а также некоторые изобретения не подлежащие патентованию например в таких областях...
46443. Методы обеспечения безопасной эксплуатации МТ 18.25 KB
  Методы обеспечения безопасной эксплуатации МТ В целях обеспечения безопасности определения фактического технического состояния объектов МТ возможности их дальнейшей эксплуатации на проектных технологических режимах для расчета допустимого давления необходимости снижения разрешенного рабочего давления и перехода на пониженные технологические режимы или необходимости ремонта с точной локализацией мест его выполнения и продления срока службы объектов МТ в процессе эксплуатации должно проводиться периодическое техническое диагностирование...
46444. Модернизм XX век 15.87 KB
  Модернизм это масштабное культурное явление которое возникло на рубеже 19 и 20 веков и затронуло практически все сферы человеческой жизни. Модернизм отрицает культурное наследие и реальное воспроизведение действительности использует деформацию образов и субъективное восприятие художника т. Модернизм объединяет множество относительно самостоятельных идейнохудожественных течений: экспрессионизм кубизм конструктивизм сюрреализм абстракционизм попарт.
46445. Организация производственной деятельности 15.95 KB
  Любая производственная деятельность начинается с моделирования идеального проекта включающего в себя: цели и задачи деятельности; способы и средства реализации целей и задач деятельности; исполнителей решающих задачи и обеспечивающих достижение целей деятельности. Моделирование деятельности наряду с организационноэкономическим проектированием является и психологическим процессом реализации личностной активности. Своеобразная готовность реализовать в процессе деятельности весь личностный комплекс мотивационнопотребностных...
46446. Абсцессы и гангрена легких. Понятие. Классификация: клинико-морфологические формы, по этиологии, по механизму проникновения повреждающего агента, по предрасполагающим факторам, по распространению, по тяжести течения 15.98 KB
  Абсцессы А и гангрена Г легких. гангрена. По распространению:I односторонние поражения 1 абсцессы а одиночные б множественные 2 гангрена а лобарная б субтотальная в тотальная II двусторонние поражения1 абсцессы множественные 2 гангрена 3 абсц одного легк и гангрена др.
46447. Органы государственной власти 15.99 KB
  Его структура официальное наименование и численность депутатов устанавливаются конституцией уставом субъекта РФ с учетом местных национальных и иных исторических особенностей. Количество депутатов законодательного представительного органа субъекта РФ устанавливается конституцией основным законом субъекта РФ. При выборах законодательного представительного органа государственной власти субъекта РФ не менее 50 процентов депутатов данного органа должны избираться по единому избирательному округу пропорционально числу голосов...