Графы и сети
Introduced| English | Русский |
|---|---|
| graph/ɡræf/ | график |
| vertices/ˈvɜːtɪsiːz/ | вершины |
| edges/ˈedʒɪz/ | края |
| degree/dɪˈɡriː/ | степени |
| path/pæθ/ | путь |
| cycle/ˈsaɪkl/ | цикл |
| connected/kəˈnektɪd/ | связный |
| tree/triː/ | дерево |
| weighted graph/ˈweɪtɪd ɡræf/ | взвешенный граф |
| shortest path/ˈʃɔːtɪst pæθ/ | кратчайший путь |
Модель связей требует своих предпосылок
- Граф имеет вершины и ребра. Решите, что они представляют и являются ли связи направленными, взвешенными или ненаправленными.
- Рабочий лист использует конечные простые ненаправленные графы без петель или кратных ребер. Позиция рисования не меняет их соединений, но стрелка или вес ребра могут изменить математическую модель.
Подсчитывайте соединения последовательно
- Степень считает инцидентные ребра в простом ненаправленном графе. Сумма степеней равна удвоенному числу ребер, поэтому она должна быть четной.
- Путь следует по соединениям; цикл возвращается в начальную точку, не повторяя другие вершины. Граф является связным, когда каждая вершина достижима из каждой другой.
В простом неориентированном графе без петель четыре ребра соединены с вершиной. Какова её степень?
Её степень равна 4, количеству инцидентных рёбер при указанной конвенции графа.
Дерево должно обладать двумя свойствами
- Дерево связно и не имеет циклов. Конечное дерево с n вершинами имеет n минус 1 ребро.
- Наличие n минус 1 ребра само по себе не доказывает дерево: треугольник плюс отдельный компонент из двух вершин имеют пять вершин и четыре ребра, но являются несвязным и циклическим.
В дереве 4 вершины. Сколько в нём рёбер?
Конечное дерево с четырьмя вершинами имеет n − 1 = 3 ребра. Этот подсчет зависит от того, что граф действительно является связным и ациклическим.
В связном неориентированном графе со строго положительными стоимостями рёбер, почему минимальный по стоимости связный подграф, охватывающий все вершины, не содержит циклов?
Удаление любого ребра цикла сохраняет связность и снижает общую стоимость, поскольку его вес строго положителен. Следовательно, подграф с циклами не может быть минимальным при данных допущениях.
Дороги с положительной стоимостью. Для связанной сети со строго положительными стоимостями дорог удаление ребра цикла сохраняет связность и снижает стоимость. Следовательно, подграф минимальной стоимости соединения является деревом. Чтобы найти остовное дерево минимального веса, выбирайте ребра, соединяющие все вершины без циклов; слепой выбор самых дешевых n минус 1 ребер может оставить отдельные компоненты.
Кратчайший маршрут не является остовным деревом
- Взвешенный граф присваивает указанное значение каждому ребру. Кратчайший путь минимизирует вес маршрута между данными конечными точками.
- Остовное дерево минимального веса вместо этого соединяет каждую вершину при минимальной общей включенной стоимости. Кратчайший маршрут может иметь больше ребер, чем прямой дорогой маршрут; суммируйте веса, а не считайте количество ребер.
Соотнесите каждую ситуацию с тем, чем должны быть её вершины и рёбра.
Решение того, что представляют вершины, — это этап моделирования, и именно здесь ставятся баллы.
Закрытие ребра изменяет допустимость. Лист 4.5 находит маршрут с весом 7, затем закрывает ребро и проверяет замену с весом 9. Не используйте старую сумму для пути, которого больше не существует.
Два рисунка, которые выглядят по-разному, обязательно представляют разные графы.
Различные layouts могут иметь одинаковую помеченную матрицу смежности. Сравнивайте также направления и веса, если они являются частью заданного графа.
Сравните все структуры, имеющие отношение к вопросу: соответствие вершин, смежность, направления и веса там, где они указаны. Визуально похожие рисунки не обязательно представляют один и тот же граф; различные макеты могут отражать одни и те же помеченные связи.