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  


 

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

20734. Проективная плоскость и ее модели. Группа проективных преобразований. Приложение к решению задач 29 KB
  Дополним прямую точкой бесконечно удаленной которую будем считать точкой соответствующей прямой х параллельной прямой а. Прямая дополненная бесконечно удаленной точкой называется проективной прямой. Плоскость дополненная бесконечно удаленной прямой называется проективной плоскостью. Пространство дополненное бесконечно удаленной плоскостью называется проективным пространством.
20735. Группа движений. Классификация 115.5 KB
  Классификация Движение такое преобразование плоскости которое сохраняет расстояние между любыми двумя точками. Это определение отличается от определений поворота симметрии и переноса тем что не является конструктивным нельзя определить как выполнять движение. Теорема: каковы бы ни были два прямоугольных декартовых репера и существует движение переводящее так что ориентация сохраняется. Если оба репера ориентированы одинаково то движение не изменяет ориентацию фигур иначе меняет на противоположную.
20736. Трехмерное евклидово пространство. Скалярное, векторное и смешанное произведение векторов. Приложение к решению задач 55.5 KB
  Скалярное векторное и смешанное произведение векторов. Основные отношения сумма векторов скалярное произведение умножение вектора на число. Аксиомы: аксиомы линейных векторов аксиома размерности аксиомы скалярного произведения. Линейное векторное пространство называется евклидовым если каждым двум векторам a и b этого пространства поставлено в соответствие число α называемое скалярным произведением этих векторов.
20737. Система аксиом Вейля трехмерного евклидова пространства и ее непротиворечивость 101 KB
  Геометрия Вопрос №11 Система аксиом Вейля трехмерного евклидова пространства и ее непротиворечивость Пусть трехмерное векторное пространство на полем вещественных чисел а непустое множество элементы которого называются точками. Предполагается также что дано множество отображений каждое из которых является отображением вида . Множество называется трехмерным вещественным евклидовым пространством если выполнены следующие аксиомы. Множество является множеством положительноопределенных билинейных форм таких что если то где .
20738. Линейные отображения (операторы). Матрица линейного оператора. Собственные векторы и собственные значения. Характеристическое уравнение 147 KB
  Матрица линейного оператора. Ядром линейного оператора называется Образом линейного оператора называется Ядро Образ Теорема. Каждый вектор разложим по базису B: Столбцы матрицы линейного оператора представляют собой координатные столбцы образов базисных векторов относительно данного базиса.АBfматрица линейного оператора.
20739. Ранг матрицы 107.5 KB
  Вопрос №11 Ранг матрицы. Столбцевым рангом матрицы называют ранг системы столбцов. Строчечным рангом матрицы называют равный столбцевому для произвольной матрицы. Согласно теореме можно говорить просто о ранге матрицы не уточняя о ранге системы строк или столбцов идет речь.
20741. Решение системы линейных уравнений методом последовательного исключения переменных. Структура множества решений системы линейных уравнений 50.5 KB
  Решение системы линейных уравнений методом последовательного исключения переменных. Структура множества решений системы линейных уравнений Метод Жордана – ГауссаМЖГ. Каждое элементарное преобразование системы является равносильным Докво: 1 – равносильное преобразование. x1xn – решение Каждому элементарному преобразованию СЛАУ соответствует элементарное преобразование строк расширенной матрицы системы.
20742. Кольцо. Примеры колец. Простейшие свойства колец. Подкольцо. Гомоморфизмы и изоморфизмы колец 128 KB
  Подкольцо. Алгебра называется кольцом если: 1 абелева группа. Если ассоциативный группоид полугруппа то ассоциативное кольцо. Если моноид существует то ассоциативное кольцо с единицей.