Работа по теме «Графы». Вариант 1. 1. На рисунке изображены графы. Сколько у каждого из них ребер, вершин; изолированных вершин? 2. На каких рисунках графы одинаковы? 3. Изобразите три разных графа, у которых три ребра, четыре вершины. Найдите сумму степеней вершин каждого графа. 4. Построить граф. В некоторой стране соединить все эти города. Строительство железного полотна стоит дорого, поэтому их количество должно быть минимальным. Но компания заботится и об удобстве жителей страны, поэтому дороги будут спроектированы так, чтобы из каждого города можно было попасть в любой, сделав не более двух пересадок. Сколько железных дорог нужно будет проложить компании? Работа по теме «Графы». Вариант 2. 1. На рисунке изображены графы. Сколько у каждого из них ребер, вершин?

Здравствуйте, ребята! Давайте разберем эти задания по графам. **Вариант 1** **1. Анализ графов на рисунке:** * **Граф а):** * Ребра: 5 * Вершины: 5 * Изолированные вершины: 1 * **Граф б):** * Ребра: 8 * Вершины: 5 * Изолированные вершины: 0 **2. Одинаковые графы:** На данном рисунке нет одинаковых графов. **3. Построение графов и сумма степеней вершин:** Нам нужно нарисовать три разных графа с тремя ребрами и четырьмя вершинами. Сумма степеней вершин каждого графа будет равна удвоенному количеству ребер. Это связано с тем, что каждое ребро соединяет две вершины, и, следовательно, учитывается в степени каждой из этих вершин. Формула: $\sum deg(v) = 2|E|$, где $deg(v)$ - степень вершины, $|E|$ - количество ребер. Для каждого графа с 3 ребрами сумма степеней вершин будет: $2 * 3 = 6$. **4. Построение графа для железнодорожной компании:** У нас 14 городов, и нужно соединить их минимальным количеством дорог, чтобы из каждого города можно было попасть в любой другой, сделав не более двух пересадок. Это означает, что граф должен быть связным. Минимальное количество ребер в связном графе с $n$ вершинами равно $n-1$. В нашем случае это дерево. Значит, нужно построить граф с 14 вершинами и 13 ребрами так, чтобы из любого города можно было добраться до любого другого не более чем с двумя пересадками. Один из вариантов – создать звезду, где один город соединен со всеми остальными. Но это не всегда оптимально с точки зрения двух пересадок. Более сбалансированный вариант - это построить граф, близкий к "цепочке" или "пути", а затем добавить несколько дополнительных ребер, чтобы сократить максимальное количество пересадок до двух. Но в любом случае, для связности нам нужно минимум 13 дорог. **Вариант 2** **1. Анализ графов на рисунке:** * **Граф а):** * Ребра: 5 * Вершины: 5 * **Граф б):** * Ребра: 5 * Вершины: 5 * **Граф в):** * Ребра: 5 * Вершины: 5 **Развернутый ответ:** В первом варианте мы определили количество ребер и вершин в представленных графах, а также наличие изолированных вершин. Обсудили, какие графы можно считать одинаковыми. Нарисовали графы с заданными параметрами и определили сумму степеней их вершин. Решили задачу о железнодорожной компании, используя концепцию связности графа. Во втором варианте определили количество ребер и вершин в графах a, b, c.