КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Что называют графом?

Привет! Давай разберемся с основами теории графов. Это очень важная тема в информатике. 1. **Граф** — это совокупность объектов (вершин) и связей между ними (ребер или дуг). 2. **Способы задания графа:** графический (рисунок), матрица смежности, матрица инцидентности, списки смежности. 3. **Петля** означает, что вершина связана сама с собой (ребро выходит из вершины и в нее же входит). 4. **Матрица смежности** показывает, какие вершины соединены между собой. **Матрица инцидентности** показывает, какие вершины принадлежат каким ребрам. 5. **Гамильтоновы графы** — это графы, содержащие гамильтонов цикл (маршрут, проходящий через каждую вершину ровно один раз). 6. **Эйлеровы графы** — это графы, содержащие эйлеров цикл (маршрут, проходящий через каждое ребро ровно один раз). 7. **Основные типы графов:** - Ориентированные (есть направление стрелок) и неориентированные (просто линии). - Взвешенные (у ребер есть «вес» или числовое значение) и невзвешенные. - Простые (без петель и кратных ребер) и мультиграфы. 8. **Путь** — это последовательность вершин, в которой каждая пара соседних вершин соединена ребром. Часто подразумевается, что ребра (иногда и вершины) не повторяются. 9. **Отличия:** - **Маршрут:** последовательность ребер, где можно повторять вершины и ребра. - **Путь (цепь):** маршрут, где нельзя повторять ребра. - **Цикл:** путь, у которого начальная и конечная вершины совпадают.