Вариант 1. B Выполните задания по рисунку: a) Найдите простой цикл графа. б) Найдите цепь графа. b)Найдите наибольшую степень вершин графа. 2. В графе n вершин, каждая из которых является смежной для остальных вершин. Сколько рёбер в графе?
Привет! Давай вместе разберемся с этими заданиями.
Задание по рисунку: а) Простой цикл графа – это цикл, который проходит через ряд вершин без повторений вершин и рёбер. Если мы посмотрим на рисунок, то можем выбрать, например, такой цикл: вершина 1 - вершина 2 - вершина 3 - вершина 4 - вершина 1. б) Цепь графа – это последовательность вершин и рёбер, где каждое последующее ребро связывает пару вершин, одна из которых была затронута предыдущим ребром, и при этом вершины и рёбра не повторяются. Пример цепи: вершина 1 - вершина 2 - вершина 3 - вершина 5. в) Наибольшая степень вершины графа – это максимальное количество рёбер, инцидентных вершине. Глядя на рисунок, можно увидеть, что у вершины 3 четыре инцидентных ребра, что представляет собой максимальную степень этого графа.
Теперь решим задачу про граф с n вершинами, где каждая вершина смежна с остальными. Такой граф называется полным, и обозначается как K_n. Количество рёбер в полном графе равно числу способов выбрать 2 вершины из n, то есть сочетанию из n по 2. Формула сочетания без повторений выглядит так: C(n, 2) = n * (n - 1) / 2. Так что в таком графе будет n*(n-1)/2 рёбер.
Если нужно будет что-то ещё, обращайся!
