Как найти степени вершин
Перейти к содержимому

Как найти степени вершин

  • автор:

Доступ к сервису временно запрещён

С вашего IP-адреса одновременно поступает очень много запросов.
Такое поведение показалось подозрительным, поэтому мы временно закрыли доступ к сайту.
Возможно, на вашем устройстве есть программы, которые отправляют запросы без вашего ведома.

Что мне делать?

Напишите в службу поддержки через форму обратной связи.
Подробно опишите ситуацию — поможем разобраться, что случилось, и подскажем, как действовать дальше.

Как найти степени вершин

Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Обозначать степени вершин А, В, Сбудем соответственно так: d(А), d(В), d(С) и т. п.
Задача 2.1.
а) Найдите степени вершин А, В, С и D.
Ответ: степ.А=1; степ.В=2; степ.С=1; степ.D=2.

б) Чему равна степень каждой вершины?
Ответ: 2
в) Чему равна степень каждой вершины?
Ответ: 0.
Степень изолированной вершины равна 0.
Вершина называется нечетной,если ее степень — число не­
четное. Вершина называется четной,если ее степень — число
четное.
Задача 2.2. Уезжая из летнего лагеря, подружившиеся ребята обменялись конвертами с адресами. Докажите, что
а) всего было передано четное число конвертов;
б) число участников, обменявшихся конвертами нечетное чис­ло раз, четное.
Решение. Пусть участники слета А1, А2, A3. Ап — вершины графа, а ребра соединяют на рисунке 15 пары вершин, изобра­жающих ребят, обменявшихся конвертами:
рис. 15
а) степень каждой вершины Ai показывает число конвертов, которые передал участник Аi своим знакомым. Общее число переданных кон­вертов N равно сумме степеней всех вершин графа. N = степ. А1+степ. А2+. +степ. Ап-1+ степ. Ап, но N = 2р, где р — число ре­бер графа, то есть N — четное. Следовательно, было передано четное число конвертов.
б) в равенстве N = степ. А1 + степ. А2 + . + степ. Ап-1 + степ. Ап сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся кон­вертами нечетное число раз, четное.
В ходе решения задачи 1 доказаны два свойства.
Свойство 1. В графе G сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа.
степ. А1 + степ. А2+ . + степ. Аn = 2р,
где р — число ребер графа Г, n — число его вершин.
Свойство 2. Число нечетных вершин любого графа четно.
Задача 2.3. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым из осталь­ных по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.
Решение. Переведем условие задачи на язык графов. Каж­дому из шахматистов поставим в соответствие вершину графа, со­единим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим между собой партию. Получим граф с девятью вер­шинами. Степени его вершин равняются числу партий, сыгранных соответствующими игроками. Покажем, что во всяком графе с де­вятью вершинами всегда найдутся хотя бы две вершины одинаковой степени.
Каждая вершина графа с девятью вершинами может иметь сте­пень, равную 0, 1, 2, . 7, 8. Предположим, что существует граф G, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, . 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действитель­но, если в графе есть вершина Астепени 0, то в нем не найдется вер­шина Всо степенью 8, так как эта вершина В должна быть соедине­на ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.
Вернемся к задаче. Доказано, что в любой момент найдутся хотя бы двое, сыгравшие одинаковое число партий.
Решение этой задачи почти дословно повторяется в ходе дока­зательства следующего свойства (только число 9 приходится заменить произвольным натуральным числом n ? 2).
Свойство 3. Во всяком графе с n вершинами, где n ? 2, всегда найдутся, по меньшей мере, две вершины с одинаковыми сте­пенями.
Задача 2.4. Девять человек проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что тогда либо в точности один участник еще не сыграл ни одной партии, либо в точности один сыграл все партии.
Решение: Условие задачи переведем на язык графов. Пусть вершины графа — игроки, а каждое ребро означает, что соответ­ствующие игроки уже сыграли между собой партию. Из условия известно, что в точности две вершины имеют одинаковые степе­ни. Требуется доказать, что в таком графе всегда найдется либо только одна изолированная вершина, либо только одна вершина степени 8.
В общем случае у графа с девятью вершинами степень каждой вершины может принимать одно из девяти значений: 0, 1, 2, . 7, 8. Но у такого графа степени вершин принимают только восемь разных значений, ибо ровно две вершины имеют одинако­вую степень. Следовательно, обязательно либо 0, либо 8 будет значением степени одной из вершин.
Докажем, что в графах с девятью вершинами, из которых в точности две имеют одинаковую степень, не может быть двух вершинстепени 0 или двух вершин степени 8. Допустим, что все же найдется граф с девятью вершинами, в котором ровно две вершины изолированные, а все остальные имеют разные между собой степени. Тогда, если не рассматривать эти две изолированные вершины, останется граф с семью вершинами, степени которых не совпадают. Но такого графа не существует (см. свойство 3). Значит, это предположение неверное.
Теперь допустим, что существует граф с девятью вершинами, в котором ровно две вершины имеют степень 8, а все остальные — несовпадающие степени. Тогда в дополнении данного графа ровно две вершины будут иметь степень 0, а остальные попарно различ­ные степени. Этого тоже не может быть (свойство 3), т. е. и второе предположение неверное.
Следовательно, у графа с девятью вершинами, из которых в точности две имеют одинаковую степень, всегда найдется либо одна изолированная вершина, либо одна вершина степени 8.
Вернемся к задаче. Как и требовалось доказать, среди рассмот­ренных девяти игроков либо только один еще не сыграл ни одной партии, либо только один сыграл уже все партии.
При решении этой задачи число 9 можно было заменить любым другим натуральным числом n > 2.
Это решение поможет вам провести доказательство следующего свойства:

Свойство 4. Если в графе с n вершинами (n > 2) в точно­сти две вершины имеют одинаковую степень, то в этом графе всег­да найдется либо в точности одна вершина степени 0, либо в точ­ности одна вершина степени n — 1.

Расчёт степени вершин

Для неорграфа степень вершин — это количество рёбер, входящих или исходящих из вершины.

Для орграфа сервис будет считать количество рёбер, исходящих из вершины.

Для использования алгоритма выберите пункт меню Алгоритмы -> Рассчитать степень вершин

Степень вершин будет написана над каждой вершиной. Вершины одинаковой степени будут одинакового цвета.

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)

Как быстро найти вершину,которая имеет наибольшее количество ребер и не соединена с данной вершиной?

Вся суть вопроса описана в названии,добавлю,что граф задаётся списком ребер.Как это сделать быстро,не перебором. (в некоторых случаях граф может быть деревом,мб это как-то поможет),сама задача:
https://acmp.ru/asp/do/index.asp?main=task&id_cour.

  • Вопрос задан более трёх лет назад
  • 758 просмотров

2 комментария

Простой 2 комментария

Не соединена непосредственно (соседство) или через промежуточные вершины? Рёбра однонаправленные или двунаправленные?

dalbio @dalbio Автор вопроса
Понял,удаляю пост
Решения вопроса 0
Ответы на вопрос 2
Wataru @wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.

В общем случае — никак. Никакого способа, кроме как просмотреть все вершины, не связанные с данной, нет.

Но обычно вам и не надо решать эту задачу один раз для конкретной вершины. Как в приведенной задаче — вам надо решить ее для всех вершин графа одновременно. Кроме того, в приведенной задаче граф — всегда дерево.

Можно, например, считать динамику — для каждого направленного ребра возвращать максимальную степень в поддереве, не считая корень этого поддерева. Если ребро ведет в лист, то ответ — минус бесконечность — вершин нет. Иначе перебираем все ребра из конца ребра (кроме обратного) и берем максимум из ДП для них и степеней концов вершин. Для поиска максимальной вершины для заданной вам надо лишь перебрать все исходящие ребра и найти максимум в ДП.

Но в этой задаче можно проще: Найдите все вершины с максимальной степенью. Если из 3 и более, то найдите среди них 2 не связанные (берете любую, потом еще одну любую. Если они связанны, то берите любую третью — она не связанна с одной из двух первых).

Если их 2, то проверьте, вдруг они не связанны. Если же они соседние или такая всего одна, то найдите в графе еще одну вершину с максимальной степенью, которая не связанна хотя бы с одной из этих двух. Чтобы это работало за линию — заведите массив и прибавьте 1 ко всем соседям каждой из 1/2 максимальных вершин. Потом смотрите на те, где стоит 0 (или 1, если максимальных две).

Также рассмотрите в качестве варианта ответа пару соседей для максимальной вершины, если она одна. Это выбрать в массиве 2 наибольших числа — делается за линию.

Почему это работает? Понятно, что в задаче надо найти пару не связанных вершин с максимальной суммой степеней. Очевидно, что в случае трех и более максимумов или двух несвязанных максимумов этот алгоритм даст самый оптимальный ответ — 2 наибольших числа в массиве. Лучше никак не сделать.

Теперь рассмотрим случай двух связанных максимальных вершин. Рассмотрим оптимальный ответ. Если в нем нет одной из максимальных вершин, то мы могли бы заменить один из концов на максимум. Мы не можем этого сделать, только если оба конца связанны с обоими максимумами, а это означало бы циклы в графе. Но у нас же дерево! Значит, оптимальный ответ обязательно содержит одну из максимальных вершин. Но мы этот вариант в алгоритме перебрали.

Остается случай из одной максимальной вершины. Опять же оптимальный ответ не содержит ее, только если его нельзя улучшить — а значит оба конца связанны с максимальной вершиной. Но этот случай мы тоже разобрали.

Ответ написан более трёх лет назад
Нравится 2 12 комментариев

lastuniverse

Роман @lastuniverse

Илья Николаевский помогите понять задачу)) Поясните пожалуйста по следующим вопросам. Дано, как я его вижу (если вижу не правильно поправьте пожалуйста)

1. Всей Галактике известна Всеобъемлющая Галактическая Магистральная Сеть, соединяющая многие звёздные системы между собой. Эта транспортная сеть объединяет n звёздных систем посредством n−1 магистралей — скоростных путей, соединяющих некоторые две звёздные системы между собой. Главной особенностью этой магистральной сети является существование между любыми двумя звёздными системами ровно одного маршрута по этой сети
я понял так:
1.1 магистраль — это ребро между 2-я вершинами?
1.2 маршрут — это последовательность магистралей, соединяющих любые 2 вершины?
1.3 любые 2 вершины имеют только 1 маршрут?
1.4 данный граф может быть только деревом, в котором любые 2 ветви могут быть соединены только через некоторую (единственную общую для них) развилку, находящуюся ближе к корню, относительно обоих ветвей?

2. Сложность постройки такой магистрали вызвано наличием развилок. Чтобы разгрузить транспортную сеть по максимуму, в любой звёздной системе существуют развилки. Развилки соединяют уникальным туннелем каждую пару магистралей, входящих в звёздную систему.
я понял так:
2.1 если вершина имеет 2 магистрали то развилка одна, если 3 магистрали то развилки уже 3, если m магистралей то количество развилок будет суммой чисел в интервале от m-1? (2 ребра = 1 развилка, 3 ребра 1+2 развилки, 4 ребра 1+2+3 развилки, 5 ребер 1+2+3+4 развилки и т.д.) То есть, количество развилок можно считать по формуле r=m*(m-1)/2, где m — число ребер у вершины?
2.2 если все вышесказанное правильно, то каким образом достигается утверждение «в любой звёздной системе существуют развилки.» ведь по факту должны существовать оконечные вершины имеющие лишь одно ребро?

3. если рассмотреть первый пример данных из задания, то при соединении вершин 1 и 3 мы получим для любой из следующих пар ([1,2] [1,3] [1,4] [2,3] [2,4]) по два возможных маршрута (правда отличающихся длинной), что противоречит условию «Главной особенностью этой магистральной сети является существование между любыми двумя звёздными системами ровно одного маршрута по этой сети.» и п.п 1.4 и 1.4?

Подскажите пожалуйста, что именно я понимаю неверно.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *