Задача. Ориентированный граф задан связями между его вершинами (например, A B означает наличие дуги из вершины А в вершину B). Нарисовать этот граф, представить его в виде матрицы смежности, вывести степень вершины каждого графа, а также полустепени захода и исхода для каждой вершины, проверить граф на наличие в нем Эйлерова пути, для заданной вершины выполнить обход графа в ширину и в глубину.10. ГрафA B B C A E E B B F C D D H H G F C G F F EНачальная вершина обхода C.По условию задачи нам дан ориентированный граф. Выполним его чертёж, отмечая стрелками направления входа и захода в вершины графа. Н а основании этого строим матрицу смежности, ставя единицу там, где есть связь между вершинами в соответствии столбец – строка.Искомая матрица смежности задаётся в виде таблицы:

	A	B	C	D	E	F	H	G
A	0	1	0	0	1	0	0	0
B	0	0	1	0	0	1	0	0
C	0	0	0	1	0	0	0	0
D	0	0	0	0	0	0	1	0
E	0	1	0	0	0	0	0	0
F	0	0	1	0	1	0	0	0
H	0	0	0	0	0	0	0	1
G	0	0	0	0	0	1	0	0

---

Множество вершин графа (их – 8):V = A, B, C, D, E, F, G , H, V = 8Множество рёбер графа (их – 11):E = A B; B C; A E; E B; B F; C D; D H; H G; F C; G F; F E = 9Найдём полустепени исхода и захода вершин:d - A =1; d + A = 2; d - B = 2; d + B = 2; d – C = 1; d + C = 2; d – D = 1; d + D = 1; d - E = 2; d + E = 1; d – H = 1; d + H = 1; d – F = 2; d + F = 2; Следовательно, степени вершин равны:dA = 3, dE = 1, dB = 4, dG = 1, dC = 3, dH = 2, dD = 2, dF = 4; Сумма степеней вершин графа: 3 + 1 + 4 + 1 + 3 + 2 + 2 + 4 = 18 = 2∙E = 2∙9В графе нет эйлерового пути, так как при обходе из вершины A выпадает ребро А,Е.Обход в глубинуПусть вершина C является начальной вершиной обхода (красим её в серый цвет).Таким образом, включаем вершину C в список обработанных вершин.Так как граф – ориентированный, то окрашиваем в серый цвет достижимую из точки C вершину D.Далее идём в вершину H, окрашиваем её . Следовательно, пройдены три вершины.Дальше мы проходим вершину G, окрасив её. Попав в вершину G и окрасив её, мы проходим в вершину F. Затем идем в вершину Е, затем в вершину В. Завершаем обход с результатом (С; D; H; G; F; E; B)Обход в ширину

1. 
   пусть стартовая вершина – С
   
2. 
   включаем С в список обработанных вершин: список = (С)
   
3. 
   помещаем в очередь смежные с С вершины, т.е. D: очередь = (D)
   
4. 
   извлекаем из очереди вершину D? т.к. она не обработана, добавляем ее в список: список = (C, D)
   
5. 
   смежные с D вершины – это H, помещаем в очередь вершину H: очередь = (Н)
   
6. 
   извлекаем из очереди вершину Н, т.к. Н не обработана, помещаем ее в список: список = (С, D, H)
   
7. 
   смежные с H вершины – это G; помещаем в очередь вершину G: очередь = (G)
   
8. 
   извлекаем из очереди вершину G, т.к. G не обработана, помещаем ее в список: список = (С, D, H, G)
   
9. 
   смежные с G вершины – это F; помещаем в очередь вершину F: очередь = (F)
   
10. 
    извлекаем из очереди вершину F, т.к. F не обработана, помещаем ее в список: список = (С, D, H, G, F)
    
11. 
    смежные с F вершины – это E и C; С – обработана, помещаем в очередь вершину Е: очередь = (Е)
    
12. 
    извлекаем из очереди вершину Е, т.к. Е не обработана, помещаем ее в список: список = (С, D, H, G, F, Е)
    
13. 
    смежные с Е вершины – это В; помещаем в очередь вершину В: очередь = (В)
    
14. 
    извлекаем из очереди вершину В, т.к. В не обработана, помещаем ее в список: список = (С, D, H, G, F, Е, В)
    
15. 
    Смежные с В вершины С и F, т.к. они уже обработаны очередь становится пустой, то поиск заканчивается с результатом (С, D, H, G, F, Е, В)
    

---

Смотрите также файлы

• Олихейко Богдан Как меняется ландшафт киберрисков в настоящее время.docx

• Программа среднего профессионального образования 40. 02. 01. Право и организация социального обеспечения соо дисциплина Право социального обеспечения Практическое задание 3.docx

• Задачи данной статьи следующие.doc

• Программа среднего профессионального образования 40. 02. 01. Право и организация социального обеспечения соо дисциплина Административное право Практическое задание 1.docx

• Программа среднего профессионального образования 40. 02. 01. Право и организация социального обеспечения.pdf