1. Нарисуйте дерево, которое имеет четыре листа, и скажите, сколько у него узлов? 2. В чем отличие между терминами
2. В чем отличие между терминами «ребро» и «дуга»?
3. Как можно определить количество ребер в неориентированном и ориентированном графе, используя весовую матрицу?
4. Подготовьте сообщение о «лемме о рукопожатиях».
* Разъяснение: Дерево с четырьмя листьями имеет 5 узлов.
Чтобы нарисовать такое дерево, мы начинаем с одного узла (называем его корневым узлом) и добавляем 4 листовых узла, которые не имеют потомков. Всего у нас будет 5 узлов, включая корневой узел.
* Пример использования: Нарисуйте дерево с 4 листьями, содержащее 5 узлов.
Задача 2:
* Разъяснение:
— Ребро в графе представляет собой связь или соединение между двумя узлами. Это может быть прямая линия или дуга, которая указывает направление от одного узла к другому. Ребро обычно не имеет направления и может быть двусторонним.
— Дуга обычно используется в ориентированных графах и представляет собой направленное соединение от одного узла к другому. Дуга имеет начальный и конечный узел и указывает на направление движения от начального к конечному узлу.
* Пример использования: Какое отличие между ребром и дугой?
Задача 3:
* Разъяснение:
— Для неориентированного графа: количество ребер можно определить, посчитав половину ненулевых элементов весовой матрицы. Если весовая матрица имеет размерность n x n, то количество ребер будет равно половине суммы всех ненулевых элементов в верхнем или нижнем треугольнике матрицы (так как граф неориентированный, каждое ребро учитывается дважды).
— Для ориентированного графа: количество ребер можно определить, посчитав все ненулевые элементы весовой матрицы.
* Пример использования: Используя весовую матрицу, определите количество ребер в неориентированном графе размерностью 4 x 4.
Задача 4:
* Разъяснение: Лемма о рукопожатиях гласит, что сумма степеней всех вершин в неориентированном графе равна удвоенному количеству ребер в графе. Или можно сказать, что сумма степеней вершин в графе равна удвоенному числу ребер.
* Пример использования: Напишите сообщение о лемме о рукопожатиях.