Условие:
1. Представьте граф матрицами смежности и инциденций
Наименование ребер выбрать самостоятельно. Опишите характеристики графа (ориентированный, смешанный или неориентированный; простой граф, мультиграф или псевдограф; связный или несвязный; полный или нет; есть или нет у него циклы, если есть, то циклы простые или элементарны (записать какие именно); планарный или нет; эйлеров или нет (если эйлеров, то записать эйлеров цикл); гамильтонов или нет (если гамильтонов, то записать гамильтонов цикл).
Пример
Задан граф:
Матрица смежности
| Vl|V2 V 3 |V4 ∣ V5 | |||||
|---|---|---|---|---|---|
| Vl | 0 | 1 | I | 0 | 1 |
| V2 | 1 | 0 | I | I | 1 |
| V3 | 0 | 1 | 0 | 0 | 0 |
| V4 | 1 | 0 | I | 0 | 1 |
| V5 | 0 | 0 | I | 0 |
Матрица инциденций
Граф простой смешанный, связный, планарный, циклический, есть циклы: простые циклы v1 - v2 -v4-v1; v 1-v 2-v 5-v 1 ; v 1-v 2-v 5-v 4-v 1 ; v 1-v 3-v 2-v 1 и т.Д. (перечислить все циклы), разделить простые циклы и элементарные циклы; эйлерова цикла нет, следовательно граф не эйлеров; граф не гамильтонов.
В ответе обязательно представить исходный граф и соответствующие матрицы. Представить в формате DOC/DOCX (MS Word) или PDF.
Решение:
Для создания графа и его представления в виде матриц смежности и инцидентности, давайте сначала определим граф. Мы создадим простой неориентированный граф с 5 вершинами и 7 ребрами. Наименование вершин: V1, V2, V3, V4, V5. Наименование ребер: 1. e1: V1 - V2 2. e2: V1 - V3 3. e3: V2 - V3 4. e4: V2 - V4 5. e5: V3 - V4 6. e6: V4 - V5 7. e7: V1 - V5 Теперь мы можем представить граф в виде матрицы смежности. Матрица смежност...
Теперь создадим матрицу инцидентности. В этой матрице строки будут представлять вершины, а столбцы - ребра. Если вершина инцидентна ребру, то в соответствующей ячейке будет стоять 1, иначе 0. Матрица инцидентности: Теперь опишем характеристики графа: 1. Граф неориентированный. 2. Граф простой (нет петель и кратных ребер). 3. Граф связный (все вершины связаны между собой). 4. Граф не полный (не все пары вершин соединены ребром). 5. Граф имеет циклы. Примеры простых циклов: - V1 - V2 - V3 - V1 - V2 - V3 - V4 - V2 - V1 - V5 - V4 - V2 - V1 - V1 - V2 - V4 - V5 - V1 - V1 - V3 - V4 - V5 - V1 6. Граф не является планарным (можно показать, что его нельзя нарисовать на плоскости без пересечений). 7. Граф не является эйлеровым, так как не все вершины имеют четную степень. 8. Граф не является гамильтоновым, так как не существует цикла, проходящего через все вершины ровно один раз. Таким образом, мы представили граф, его матрицы смежности и инцидентности, а также описали его характеристики.