Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2020-10-20 | 498 |
5.00
из
|
Заказать работу |
|
|
В теории графов применяются:
1. Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит -1 в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.
2. Матрица смежности. Это матрица n*n где n – число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у и bij = 0 в противном случае.
3. Пусть G=(X,U) - связный граф, а - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины (пути из ) называется расстоянием между вершинами и обозначается . Положим , если вершины не соединены маршрутом (путем). Расстояние удовлетворяет следующим аксиомам:
1) ;
2) ;
3) тогда и только тогда, когда ;
4) для симметрических графов;
5) (неравенство треугольника).
4. Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:
Матрицу расстояний можно определить
5. Для фиксированной вершины величина
называется эксцентриситетом (отклоненностью) вершины .
6. Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):
7. Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):
|
8. Вершина, имеющая минимальный эксцентриситет, называется центром графа.
9. Для вершины число называется передаточным числом.
10. Вершина графа, которой соответствует минимальное передаточное число
называется медианой графа. Центров и медиан в графе может быть несколько.
Рис. 1
Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:
Радиус графа равен 1, диаметр равен 2. Центр графа - вершина ; Медиана графа - вершина .
Контрольные вопросы:
1. Что такое граф?
2. Приведите разновидности графов.
3. Может ли пустой граф быть ориентированным?
4. Нарисуйте полный граф.
5. Что такое подграф?
6. Каким образом понятие дерева активно используется в информатике и программировании?
7. Метрические характеристики графов.
Тема 4.2.Остовы графов, деревья
Деревья
Определение: Деревом называют связный граф без циклов. Пример: Название достаточно жизненно - взгляните на рисунок:
Теорема: В любом дереве вершин ровно на одну больше, чем ребер.
Док-во: Будем доказывать этот факт индукцией по количеству вершин.
Когда вершин - две ясно, что ребро ровно одно, так что база индукции очевидна.
Переход: Возьмем любое дерево. В нем есть висячая вершина. Уберем ее вместе с ребром, которое к ней ведет. Оставшееся по-прежнему будет деревом, т.к. циклы появиться не могли, и связность нарушиться тоже не могла. Но тогда в остатке вершин на одну больше, чем ребер по предположению индукции, а значит и в исходном графе тоже, т.к. есть одна дополнительная вершина и одно ребро.
Теорема: В любом связном графе с n вершинами хотя бы n -1 ребро, причем если количество ребер ровно n -1, то это дерево.
Док-во: Пусть это не дерево (иначе ребер ровно n-1 по предыдущей теореме), значит, в нем есть цикл. Сотрем любое из ребер этого цикла - граф останется связным. Если в нем остался еще цикл, то сотрем ребро и из него, и т.д. Ясно, что граф все время остается связным, так что в конце получится связный граф без циклов - дерево - у него ровно n-1 ребро, а значит у исходного графа хотя бы п.
|
.
Теорема: Следующие утверждения равносильны:
Граф является деревом.
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!