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  


 

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

24737. Перечислить и дать характеристику основным причинам сложности программного обеспечения. Общие признаки любой сложной системы; приемы борьбы со сложностью ПО 328 KB
  Модульность это представление системы в виде совокупности обособленных сегментов связь между которыми обеспечивается посредством связей между классами определяемыми в этих сегментах. Ещё бывает динамический полиморфизм при котором реализация функциичлена класса выбирается в зависимости от фактического типа указателя на объект через который она вызывается. Общее понятие класса языка С. Синтаксис описания класса.
24738. Теория языков программирования и методы трансляции 233.96 KB
  Если синтаксический анализ предназначен для распознавания и проверки правильности различных конструкций языка с точки зрения их синтаксиса структуры то семантический анализ предназначен для контроля этих конструкций с точки зрения их смыслового содержания. Фаза генерации кода предназначена для перевода промежуточной программы на машинный язык мы будем предполагать коды Ассемблера. Языки...
24739. Системы искусственного интеллекта. Модель логики предикатов первого порядка 418.5 KB
  Задаваемые при описании формальной системы правила вывода называют также правилами вывода заключений т. Различают два типа правил вывода. Правила вывода. Правила вывода устанавливают отношения на множестве формул исчисления высказываний.
24740. Линейные списки – стеки, очереди, деки. Набор процедур для работы со связанным стеком, очередью 1.08 MB
  Способы обхода бинарного дерева. Древовидная структура это конечное множество содержащее один или более узлов n такое что: 1 имеется один специально обозначенный узел называемый корнем данного дерева. Линия связи между парой узлов дерева называется обычно ветвью. Те узлы которые не ссылаются ни на какие другие узлы дерева называются листьями или терминальными вершинами рис.
24741. English Speaking Countries 17.49 KB
  The Commonwealth of Australia territories are the continent of Australia the island of Tasmania and number of smaller islands. Australia has an area of nearly eight million square kilometres. The population of Australia is over sixteen million people.
24742. Outstanding people of Russia Federation 16.41 KB
  The names of Russian scientists and writers poets composers and painters are worldfamous Pushkin Lermontov Chehov Levitan. It is almost impossible to name a branch of science in the development of which the Russian scientists haven't played the greatest role. Works of our Russian writes and poets are translated into many languages.
24743. Службы разрешения имен DNS и WINS 15.76 KB
  Для решения этой проблемы Windows XP и Windows Server 2003 обеспечивают возможность сопоставления разрешения IPадреса с именем компьютера. В состав Windows XP и Windows Server 2003 входят также две службы обеспечивающие централизованное хранение информации о соответствии имен компьютеров IPадресам и обслуживание запросов на поиск такого соответствия: служба WINS Windows Internet Name Service обеспечивающая управление именами NetBIOS. Эта служба включена для поддержки клиентских компьютеров управляемых версиями Windows 9x Me NT; ...
24744. Сетевая технология 23.5 KB
  Принципиально эти решения можно разделить на три группы: передача разных типов трафика по отдельным физическим линиям создание двух независимых сетевых инфраструктур; передача различных типов трафика по одной линии; преобразование одного вида трафика в другой с последующей транспортировкой и коммутацией.
24745. Физическая структуризация сетей. Примеры 26.36 KB
  Примеры Для построения простейшей односегментной сети достаточно иметь сетевые адаптеры и кабель подходящего типа. Повторитель улучшает электрические характеристики сигналов и их синхронность и за счет этого появляется возможность увеличивать общую длину кабеля между самыми удаленными в сети станциями. Логический сегмент построенный с использованием концентраторов Появление устройств централизующих соединения между отдельными сетевыми устройствами потенциально позволяет улучшить управляемость сети и ее эксплуатационные характеристики...