Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Упражнения.




1.1. Дан граф G

 

V6

 

 
 
v4


 

 

a) определить – к какому типу относится граф;

V5
б) найти (v1), v5);

в) указать кратности ребер (v1, v2), (v3, v5);

 
V4
V3
г) найти один из подграфов графа G;

д) указать имеющиеся циклы, простые циклы;

е) указать ребра, смежные ребру (v1, v2);

ж) какие вершины инцидентны ребру (v6, v5)?

1.2. Составить матрицы смежности и инцидентности графов:

v2
v2
а) б)

v1
 
v3
а)

 

 
 
v4



 

в)

 

Какими свойствами обладают данные матрицы?

1.3. Орграф задан матрицей инцидентности. Не строя графа, определить какие имеются контуры в графе. Какова полустепень исхода вершин v1, v4 и полустепень захода вершины v3.

1.4. Орграф задан матрицей смежности. Выяснить, имеются ли контуры в графе.

а) б) в)

1.5. Орграф D c множеством вершин V{1, 2, 3, 4, 5, 6, 7} задан списком ребер X = {(1, 4), (1, 6), (2, 1), (2, 2), (2, 6), (2, 6), (3, 2), (3, 4), (4, 6), (5, 2), (5, 4), (5, 4), (5, 5), (6.2), (6, 5), (7, 1), (7, 6)}.

Построить реализацию графа D.

1.6. Зная матрицу смежности ориентированного псевдографа, определить количество путей длины 1, 2, 3 из v3 в v2, из v2 в v4.Имеет ли контур данный орграф?

А(D) =

1.7. С помощью матрицы A(D) определить, сколько путей длины 2, 3, 4 существует из вершины v1 в вершину v2:

А(D) =

Построить граф и найти эти пути.

1.8. Даны графы G1 и G2. Построить графы G1UG2, G1×G2.

б
§ 2. Булевы матрицы

Определение: (m x n) – матрицу C= [сij], у которой сij {0;1}, где i = 1,2,…,m; j = 1,2,…,n будем называть булевойматрицей.

Замечание. В случае, если G граф без кратных ребер, то матрица смежности A(G) состоит из нулей и единиц, т.е. является булевой.

Над булевыми матрицами одинаковой размерности будем производить обычные логические операции.

1) Дизъюнкция (конъюкция)

Если C=[сij] и Д=[dij] – матрицы размерности m x n, то F=[fij]=C Д (С Д), есть матрица размерности m x n, у которой каждый элемент fij определяется следующим образом: fij= сij dijij dij) (i=1,2…,m; j=1,2…,n).

2) Логическоеумножение

Пусть C= [сij] – булева матрица размерности m x k, Д=[dij] – булева матрица размерности kxn. Тогда F= [fij]=C*Д – булева матрица размерности m x n, у которой каждый элемент fij определяется следующим образом:

fij=

Если К=С1* С2*…* Сk , причем С1= С2=…= Сk= С где С – квадратичная булева матрица, то будем писать .

Введем теперь операцию sign перехода от произвольной m x n матрицы Д=[dij] c неотрицательными элементами к булевой m x n матрице С= [cij]=signД, у которой cij=sign dij (i=1,2,…,m; j=1,2…,n), где для любого числа t 0: .

Свойства операции sign:

Sign(Д12) = sign Д1 sign Д2

Sign(Д1×Д2) = sign Д1 * sign Д2

Замечание. Булевы матрицы более экономичны в вычислительном отношении, чем целочисленные. Запоминание булевой матрицы требует меньшего объема оперативной памяти ЭВМ, чем запоминание целочисленной матрицы той же размерности. Кроме того, выполнение на ЭВМ логических операций над булевыми матрицами требует меньшего объема вычислений, чем над целочисленными.

Вернемся к задаче о вычислении наличия контуров в орграфе.

Утверждение: Для того, чтобы n-вершинный орграф Д c матрицей смежности А=А(Д) имел хотя бы один контур, необходимо и достаточно, чтобы матрица имела ненулевые диагональные элементы.


Поделиться:

Дата добавления: 2015-01-29; просмотров: 112; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты