16 / 16 / 6
Регистрация: 27.12.2010
Сообщений: 163
1

Поиск вершины с максимальной степенью в двудольном графе

25.02.2018, 12:15. Показов 2102. Ответов 4
Метки нет (Все метки)

Здравствуйте, имеется двудольный граф (X, Y).
X - это пары целых чисел [a, b]
Y - это просто целые числа: k
и [a, b] смежно k <=> a <= k <= b
Нужно найти вершину из Y с максимальной степенью (если их несколько то первую). В X вершин мало, но в Y очень много, и простой перебор не работает. Как быть?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.02.2018, 12:15
Ответы с готовыми решениями:

Графы: поиск в ширину, поиск вершины с максимальной степенью
Дан граф. Способ представления и метод обхода равен список смежности;поиск в ширину....

Доказать,что в любом графе с n вершинами есть минимум две вершины с одинаковой степенью
Помогите пожалуйста доказать,что в любом графе с n вершинами есть минимум две вершины с одинаковой...

Поиск вершины в графе по алгоритму Флойда
Добрый час суток! Есть такая задача : Написать программу в которой будет выполняться алгоритм...

Поиск всевозможных путей в графе из заданной вершины
Доброго времени суток! Есть задача: найти всевозможные пути из заданной вершины неориентированного...

4
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
25.02.2018, 14:41 2
Цитата Сообщение от mikelll Посмотреть сообщение
В X вершин мало, но в Y очень много, и простой перебор не работает.
Все вершины из Y придётся перебрать в любом случае. Или Вы чего-то не договариваете?
0
16 / 16 / 6
Регистрация: 27.12.2010
Сообщений: 163
25.02.2018, 15:56  [ТС] 3
Цитата Сообщение от Shamil1 Посмотреть сообщение
Все вершины из Y придётся перебрать в любом случае. Или Вы чего-то не договариваете?
Видимо что-то недоговариваю: изначально задача формулируется так:
Есть n - отрезков [a, b], 0 <= a < b <= 1000000000, 0 < n < 1000, некоторые из них пересекаются, нужно найти первую точку в которой пересекаются наибольшее число отрезков
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
25.02.2018, 16:14 4
вам всего лишь нужно найти точку, в которой пересекается наибольшее число отрезков. при числе отрезков до 1000 это делается очень просто за квадрат поддержанием левой и правой границы пересечения.
просто на всякий случай скажу, что при больших количествах отрезков решается методом сканирующей прямой.
0
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
25.02.2018, 19:30 5
Лучший ответ Сообщение было отмечено mikelll как решение

Решение

По-моему, можно за logn отсортировать (отдельно) левые и правые границы отрезков, а затем пройтись по ним, добавляя количество за левые границы и вычитая за правые.
Как-то так:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solve(a):
    al = sorted(map(lambda x: x[0], a))
    ar = sorted(map(lambda x: x[1], a))
    i, j = 1, 0
    max_x, max_cnt, cnt = al[0], 1, 1
    while True:
        while i < len(al) and al[i] <= ar[j]:
            cnt += 1
            i += 1
        if cnt > max_cnt:
            max_x, max_cnt = al[i-1], cnt
        if i >= len(al):
            return (max_x, max_cnt)
        while ar[j] < al[i]:
            cnt -= 1
            j += 1
(На нормальном языке всё это можно было бы в 3 строчки записать)

Добавлено через 32 минуты
Функциональный вариант кода:
Python
1
2
3
def solve(a):
    points = sorted((y for x in a for y in [(x[0],1),(x[1],-1)]), key=lambda x: (x[0],-x[1]))
    return min(accumulate(points, lambda x,y: (y[0],x[1]+y[1])), key=lambda x: (-x[1],x[0]))[0]
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.02.2018, 19:30
Помогаю со студенческими работами здесь

Поиск максимальной клики на графе
Есть программа для поиска клик на графе, ввод структуры (списка)смежности в ней происходит из файла...

поиск цикла максимальной длинны в графе
Никто не подскажет как в неориентированном графе можно найти цикл максимальной длинны, включающий...

Выбрать минимальное количество вершин в двудольном неориентированном графе
У нас есть двудольный неориентированный граф. Нужно выбрать минимальное количество вершин так,...

Разработайте программу реализующую поиск в ширину в графе из заданной вершины
Лекции пропустил теперь незнаю как написать=( выручайте.. 1.Разработайте программу с очередью....

Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе)
UNIT1 unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes,...

В заданном графе найдите все вершины, растояние от которых до заданной вершины равно 2
гласит так: &quot;В заданном графе найдите все вершины, растояние от которых до заданной вершины равно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru