Заполните таблицу, подобрав алгоритму конкретное содержание.
No п/п |
Алгоритм | Конкретное соответствие задания заданному алгоритму |
1 | Построить реализацию графа G | Изображения вершин 1, 2, ..., 7 удобно поместить (приблизительно) в вершинах правильного 7-угольника. Соединить
пары вершин в соответствии со списком дуг, избегая пересечения трех ребер в одной точке. Обозначить стрелками ориентацию дуг.
![]() |
2 | Построить матрицу инциденций графа G | Число ребер графа G - 18. В прямоугольной матрице А=||ai,j|| размерности 7х18 последовательно заполнять столбцы в соответствии со списком дуг: каждой дуге ek=(i,j), где i<>j соответствуют элементы aik=-1 u ajk=+1. Петле ek=(i,j) соответствует элемент ajk=2 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
1 | -1 | -1 | 1 | 1 | ||||||||||||||
2 | -1 | 2 | -1 | -1 | 1 | 1 | 1 | |||||||||||
3 | -1 | -1 | -1 | |||||||||||||||
4 | 1 | 1 | -1 | 1 | 1 | |||||||||||||
5 | -1 | -1 | -1 | 2 | 1 | |||||||||||||
6 | 1 | 1 | 1 | 1 | 1 | -1 | -1 | 1 | ||||||||||
7 | -1 | -1 |
3 | Построить матрицу соседства вершин графа G | В квадратной матрице В=||bij|| размерности 7х7 каждой дуге ek=(i,j) сооветствует элемент bij=1, кроме кратных дуг, которым соответствует элемент, равный кратности дуги (i,j) |
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
2 | 1 | 1 | 0 | 0 | 0 | 2 | 0 |
3 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
5 | 0 | 1 | 0 | 2 | 1 | 0 | 0 |
6 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
7 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
4 | Для соотнесенного неориентированного графа G построить матрицу соседства вершин | Квадратная матрица С=||сij|| размерности 7х7 строится из предыдущей матрицы В следующим образом: сij=cji=bij+bji для i<>j; cii=bii |
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
2 | 1 | 1 | 1 | 0 | 1 | 3 | 0 |
3 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
4 | 1 | 0 | 1 | 0 | 2 | 1 | 0 |
5 | 0 | 1 | 0 | 2 | 1 | 1 | 0 |
6 | 1 | 3 | 1 | 1 | 1 | 0 | 1 |
7 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
Заполните таблицу подобрав алгоритму конкретное содержание
No п/п |
Алгоритм | Конкретное соответствие задания заданному алгоритму | ||||
1 | Построить реализацию графа G | Процесс построения реализации графа описан в тренинге умения 1 ![]() |
||||
2 | Найти цикломатическое число графа G | Цикломатическое число, равное размерности базиса циклов графа, определяется формулой ν=p-b+k, где р - число ребер, b - число вершин, k - число компонент связности графа p=13, b=7, k=1 (нетрудно убедиться, что граф G - связный). Следовательно ν=13-7+1. | ||||
3 | Выбрать остов графа G | Поскольку число вершин графа G равно 7, в любом его остове должно быть 6 ребер. При заданном упорядочении вершин 1-7, начиная с вершины 1, последовательно добавляем ребра, присоединяющие к строящемуся дереву новую вершину: (1,2),(1,4),(1,6),(1,7),(2,3),(2,5) | ||||
4 | Построить базис циклов графа G |
1. Составим список хорд относительно построенного остова (все остальные ребра графа): (2,6),(3,4),(3,6),(4,5),(4,6),(5,6),(5,7). Число хорд должно быть равно цикломатическому числу графа, т.е. 7. 2. Поочередно присоединяя к остову по одной хорде, выделяем элементарный цикл, состоящий из этой хорды и части ребер остова - единственной цепи, связывающей в остове концы хорды.
3. Выразим в построенном базисе элементарный цикл С=(6,2,1,4,5,6). Он получается сложением по модулю 2 тех базисных циклов, которые содержат хорды, принадлежащие С (Они отмечены звездочкой в предыдущей таблице: (6,2),(4,5),(5,6)) Проверьте, что ребра цикла С содержатся в совокупности базисных циклов нечетное число раз (в частности, все хорды - ровно по одному разу), а ребра, не принадлежащие С (например, ребро (5,2)), - четное. |
На рисунке 1 изображены графы G1 - G12 с четырьмя вершинами в каждом. Сравнить графы.
Результаты сравнения графов таковы:
G1 - G7 - неориентированные; G8 - G12 - ориентмированные;
G1, G2 - полные, причем G1 = G2;
G7 - не является полным, так как хотя каждая пара вершин и соединена ребром, но имеется одна петля. (Иногда полным называют граф с петлями во всех вершинах, каждая пара которых соединена ребром. Граф G7 не отвечает и этому определению.)
G3 - все вершины этого графа являются изолированными (граф с пустым множеством ребер, т.е. Е=ø);
G4 и G5 являются дополнением друг другу: G4 = ┐G5 и G5 = G4;
G6 - мультиграф, так как содержит кратные ребра a и b, а также e и f;
G8 - ориентированный, канонически соответствующий неориентированному графу G;
G9 и G10 не являются равными, так как имеют отличающиеся ребра: (4, 1) - в G9 и (1, 4) - в G10;
G11 - ориентированный мультиграф: ребра a и b - кратные, тогда как G12 мультиграфом не является, поскольку в нем ребра a и b различно ориентированы.
Задать граф G1, представленный на рисунке 2, через множества вершин V1 и ребер E1.
Граф G1 может быть полностью определен:
Порядок указания вершин при описании ребра здесь безразличен, так как все ребра в графе G неориентированные.
Матрицы инцидентности графов G1 и G3 приведены в таблице 5.1. В матрице инцидентности в каждом столбце
только два элемента, отличных от 0 (или один, если ребро - петля). Список ребер является более компактным опиманием графа. Список ребер
орграфа G3 приведен в таблице 5.3, для неориентированного графа G1 он аналогичен, однако последовательность
указания вершин здесь безразлична. Матрицы смежности графов G1, G3 даны в таблице 5.2.
G1 | a | b | c | d | e | f | g | G3 | a | b | c | d | e | f | g | |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | -1 | 1 | -1 | 0 | 0 | 0 | 0 | |
2 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 2 | 1 | -1 | 0 | -1 | -1 | 0 | 0 | |
3 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 3 | 0 | 0 | 1 | 1 | 0 | -1 | 0 | |
4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 4 | 0 | 0 | 0 | 0 | 1 | 1 | 2 |
G1 | 1 | 2 | 3 | 4 | G3 | 1 | 2 | 3 | 4 | |
1 | 0 | 2 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | |
2 | 2 | 0 | 1 | 1 | 2 | 1 | 0 | 1 | 1 | |
3 | 1 | 1 | 0 | 1 | 3 | 0 | 0 | 0 | 1 | |
4 | 0 | 1 | 1 | 1 | 4 | 0 | 0 | 0 | 1 |
Ребро | Вершины |
a | 1 2 |
b | 2 1 |
c | 1 3 |
d | 2 3 |
e | 2 4 |
f | 3 4 |
g | 4 4 |