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  


 

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

29618. Контент-анализ документов в социологическом исследовании. Основные процедуры методы 28 KB
  Контентанализ – строго формализованный вид анализа документальной информации суть которого состоит в переводе её в количественные показатели с последующей математической обработкой. Процедура контентанализа включает в себя: выделение смысловых единиц анализа категорий анализа определение единиц счета индикаторов характеристик в тексте анализа соответствующих выделенным смысловым единицам. Смысловые единицы категории анализа – это направления анализа текста некие теоретические конструкты или эмпирические обобщения...
29619. Эксперимент как метод социологического исследования. Логика экспериментального анализа 28 KB
  Логика экспериментального анализа. Метод эксперимента в социологии используется не столь часто как опросные методы и метод наблюдения. Итак эксперимент – это опытное исследование воздействия отдельного фактора или нескольких факторов на интересующую исследователя переменную.
29620. Виды эксперимента. Мысленный эксперимент в социологическом исследовании 42 KB
  Существует несколько видов эксперимента среди которых чаще всего выделяют: лабораторный полевой натурный мысленный Мысленный эксперимент проводится в логике натурного эксперимента допосле с контрольной группой. Этапы: Разделение всего массива анкет на 2 группы – экспериментальную и контрольную. Выделение этих двух групп происходит следующим образом: в экспериментальную группу попадают те анкеты в которых отмечены положительные пункты шкалы интереса 1 и 2.
29621. Организационно-логический план эксперимента 21.5 KB
  В социологических исследованиях используются четыре организационнологических плана исследования: Эксперимент допосле без контрольной группы. Эксперимент допосле с контрольной группой. Эксперимент только после с контрольной группой. Эксперимент якобы допосле с контрольной группой.
29622. Способы выравнивания групп в социологическом исследовании 33.5 KB
  Мужчина 40 лет 10 классов образования; Женат; Слесарь 3го разряда.А; Женщина; 8 классов образования; 32 года; замужем; контролёр 2го разряда.П; Мужчина; 10 классов образования; 40 лет; Женат; Слесарь 3го разряда.А; Женщина; 8 классов образования; 32 года; замужем; контролёр 2го разряда.
29623. Социометрический опрос в социологическом исследовании. Назначение, опыт использования 23 KB
  Производственные критерии – это критерии позволяющие выяснить межличностные взаимоотношения на уровне структуры производственной учебной деятельности Например: Кого бы Вы выбрали напарником Непроизводственные критерии – это критерии являющиеся показателями межличностных отношений в коллективе С кем Вы хотели бы пойти в поход. Прогностические критерии – это критерии позволяющие выяснить структуру ожидания отношений членов коллектива согласно представлениям респондентов. Респонденту предлагается ответить на вопрос кто из членов...
29624. Процедура проведения социометрического опроса 27 KB
  Теперь исходя из практики исследований оптимальным принято считать численный состав малой группы в 1020 человек. При социометрическом опросе каждому опрашиваемому вручается социометрическая анкета социометрическая карточка и список членов социометрируемой группы. Для удобства работы и простоты последующей обработки фамилии членов группы шифруются или кодируются номером в списке группы. Проранжируйте пожалуйста членов Вашей группы по степени симпатии к ним сначала назовите самого близкого для Вас товарища потом менее близкого и т.
29625. Обработка данных социометрического опроса: социометрическая матрица 31.5 KB
  Персональные социометрические индексы – это отражение индивидуальных социальнопсихологических свойств личности проявляющихся в отношении к членам группы. Социометрический статус – персональный социометрический индекс отражающий отношение членов группы к каждому её представителю выбор отвержение опускание. Персональный социометрический статус вычисляется по формуле: Ci = где Ci социометрический статус R и R положительные и отрицательные выборы полученные i членом группы. N – число членов группы Индекс эмоциональной...
29626. Обработка данных социометрического опроса: социограммы 26.5 KB
  Графическое изображение связей внутри коллектива устанавливаемых на основании выбора называется социограммой. Его выделение важно при изучении функциональных связей рабочего коллектива или эмоциональнопсихологических связей симпатий внутри коллектива. Связь между двумя элементами – Диада структура очень часто наблюдаемая в небольших коллективах например в форме совместной деятельности а также как дружеские и доверительные связи между двумя людьми. В круговых социограммах все члены коллектива располагаются по окружности внутри...