Дай ответ
Привет! Давай вместе решим эти задачи по графам.
- Начнем с подсчета ребер и вершин для каждого графа на рисунке.
а) В графе а) 5 вершин и 5 ребер. б) В графе б) 5 вершин и 7 ребер.
- Теперь определим, на каких рисунках графы одинаковые, т.е. изоморфные.
На рисунках б) и в) изображены одинаковые (изоморфные) графы. Это можно увидеть, проследив, как вершины соединены между собой: в обоих случаях есть три вершины, из каждой из которых выходит по два ребра, и две вершины, из каждой выходит по три ребра.
- А сейчас давай нарисуем три разных графа, у каждого из которых три ребра и четыре вершины.
Например, представь себе треугольник (это даст нам три вершины и три ребра), а затем добавь четвертую вершину, которая не соединена с другими (изолированная вершина).
Сумма степеней вершин каждого графа будет равна удвоенному количеству ребер, так как каждое ребро увеличивает степень двух вершин на 1. Таким образом, в нашем примере графа у нас две вершины со степенью 2 и одна вершина со степенью 1 (две вершины формируют одно ребро, а каждая из них еще соединена с третьей вершиной, которая тоже будет иметь степень 2), плюс одна изолированная вершина со степенью 0. Сумма степеней будет 2+2+1+0=5 для каждого графа.
