Задание 5. Построить плоское изображение графа, если это возможно.
Пример выполнения задания №5.
Под «если это возможно» имеется в виду без пересечения ребер. Суть задания в этом (определить, планарный ли граф). В вашем случае вершины 2, 6 можно разместить в середине, 3 и 5 – внизу, тогда пересечений не будет.
п
Пример выполнения задания №6.
Количество вершин: 11;
Количество рёбер: 15;
Степень вершин 1, 2, 3, 5, 8, 11 = 2;
Степень вершин 6, 12, 13 = 3;
Степень вершины 7 = 4;
Степень вершины 10 = 5;
Матрица смежности
| 1 | 2 | 3 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 10 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 12 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 13 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1-2 | 1-3 | 2-3 | 5-6 | 5-10 | 6-7 | 6-10 | 7-10 | 7-8 | 7-12 | 8-12 | 10-11 | 10-13 | 11-13 | 12-13 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 13 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
Матрица инцидентности
|
|
|
ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
Необходимо построить Транспортную систему внутри производства, где граф – транспортная система, узлы – отсеки цехов, рёбра – конвейеры, удаление рёбер и узлов – соответствующее им удаление отсека или пути в транспортной системе.
|
|
|
Задание 4.
Варианты 1-30. Для данного неориентированного графа составить матрицы смежности и инциденции, определить связность, число ребер, вершин и степень каждой вершины. Преобразовать данный неориентированный граф в орграф и составить для него матрицы смежности и инциденции. Начертить оба графа.
Рекомендуемая литература
1. Дистель Р. Теория графов Пер. с англ. - Новосибирск: Издательство института математики, 2002.
2. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. — М.: Высш. школа, 1976.
3. Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
4. Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.
Дата добавления: 2020-12-12; просмотров: 172; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!