Описание тега bipartite

Вопросы с тегом
Двудольный граф (он же биграф) - это граф, вершины которого можно разделить на два непересекающихся множества, так что вершины из одного набора соединяются только с вершинами из другого набора, а не друг с другом. Приложения, в которых они возникают, включают планирование ресурсов и теорию кодирования.
1 ответ

Расширение максимального соответствия двудольного графа

Предположим, что есть два таких графика: Мы стремимся найти совпадающие соответствия между двумя графами. И теперь мы используем метод, чтобы вычислить сходство двух узлов между двумя графами. w(A,1) означает сходство узла A с левого графа между узл…
27 ноя '15 в 02:37
0 ответов

Как найти, если данный граф можно разложить на когти?

Я дал граф, где каждая вершина имеет ровно 3 ребра. Теперь я должен выяснить, можно ли граф разложить на когти или нет. Я знаю, если граф является двудольным графом, чем его можно разложить на когти, я не могу понять, как когти связаны с двухсторонн…
14 окт '13 в 08:38
1 ответ

Остановить обрезку кромок в двудольном пакете (plotweb)

С помощью функции plotweb() в пакете двудольных в R я создал сеть, но некоторые метки слишком длинны для области графика. В результате они обрезаются сверху и снизу (я включил картинку). Я пытаюсь привести его в соответствие с графиком, или, если эт…
03 дек '18 в 11:16
4 ответа

Полностью отключить двудольный граф

У меня есть несвязный двунаправленный неориентированный граф. Я хочу полностью отключить график. Единственная операция, которую я могу выполнить - это удалить узел. Удаление узла автоматически удалит его ребра. Задача - минимизировать количество уда…
06 авг '12 в 19:46
1 ответ

Найти отображение в двудольном графе

Существует квадратная двоичная матрица, которая обозначает связи в двудольном графе. Вопрос в том, существует ли взаимно-однозначное сопоставление всех строк и столбцов? (Для ясности, если я использую неправильный язык, полностью связанный граф удов…
05 май '11 в 01:23
0 ответов

Плотные и разреженные двудольные графы

В чем разница между плотным и разреженным двудольным графом? Одинаково ли вычислено ребро для обоих, используя k(m,n) = m*n для разреженного и k(m,n) = m+n+1 для плотного?
23 окт '17 в 22:07
1 ответ

Сопоставление максимальных весов с взвешенными вершинами

У меня есть двудольный граф с двумя наборами вершин A и B. Края не имеют весов. Однако вершинам в одном из наборов (скажем, в наборе B) назначены положительные веса (wb1,wb2...). Я хочу найти соответствие в этом двудольном графе, чтобы максимизирова…
02 янв '16 в 20:27
2 ответа

Теорема об интегральности в максимальном потоке

Теорема об интегральности говорит нам, что если все емкости в сети потока являются целыми числами, то существует максимальный поток, где каждое значение является целым числом Но самая замечательная часть - это существование, а не каждый максимальный…
22 дек '13 в 18:57
1 ответ

Максимальная мощность в двудольном графе

Является ли максимальная мощность в двудольном графе такой же, как максимальный поток в этом графе с двумя фиктивными узлами, один из которых является источником, а другой - приемником. Источник связан с одним набором двудольных графов, а другой наб…
23 сен '14 в 18:35
0 ответов

Матрица инцидентности для двудольных групп с несколькими объединениями

Мне было интересно, есть ли быстрый способ получить матрицу заболеваемости для такой проблемы. У меня есть два фрейма данных с тремя столбцами (ключи объединения) df1 <- data.frame(K1=c(1,1,0,1,3,2,2),K2=c(1,2,1,0,2,0,1),K3=c(0,0,3,2,1,3,0)) df2 …
15 июн '16 в 09:10
1 ответ

nx.bipartite.biadjacency_matrix() - отслеживание узлов

Я использую Python 3.6 и Networkx 2.1. Я импортирую двудольный граф из взвешенного списка ребер, а затем вызываю матричную функцию двунаправленности и преобразовываю результат в кадр данных pandas для выполнения некоторых операций над ним, например,…
24 янв '18 в 10:30
2 ответа

Использование цикла для создания нового списка из предыдущего списка в r

Я выполняю функцию (computeModules{bipartite}), которая выдает разные результаты при каждом запуске. Я хочу повторить выполнение 100 раз. Вывод функции состоит из списка с несколькими слотами. Мне нужно извлечь матрицу из одного из этих слотов (@mod…
16 дек '14 в 13:03
1 ответ

Комбинации "продуктов" для формирования стимулирования сбыта

Я перерабатываю унаследованную систему, которая объединяет корзину выбранных пользователем розничных продуктов в одну или несколько действительных рекламных акций. Эти акции являются отраслевым стандартом BOGOF (купи одно, получи одно бесплатно), ку…
26 ноя '12 в 11:21
1 ответ

Граф для двудольного графа путем удаления ребер (не более чем ребер /2) - алгоритм?

Скажем, у нас есть график, и вам разрешено удалять ребра (не более (ребра исходного графа)/2) до тех пор, пока это не будет двудольный граф. Допустим, нам дали: E={ (4, 1),( 1 ,2), (2 ,3),( 7, 2),( 1 ,5),( 8 ,4), (5 ,8),( 8, 9)} и множество вершин: …
04 дек '17 в 05:06
1 ответ

Верно / Неверно "Количество циклов в двудольном графе может быть нечетным"

У меня есть заявление. "Число циклов в двудольном графе может быть нечетным" Я думаю, что это "ложь", потому что число циклов в двудольном может быть четным или нечетным. Например, На приведенном ниже двудольном графике (первая диаграмма) всего 1 ци…
28 сен '17 в 20:46
0 ответов

Создание подграфа с использованием двухсторонней сети

У меня есть набор фильмов и актеров - каждая строка представляет собой комбинацию двух. Я хочу создать график, в котором фильмы связаны, когда они делят двух или более актеров. Список актеров сохраняется в переменной ctors.2000. Я уже провел такой а…
04 мар '17 в 14:50
1 ответ

Как создать атрибут type для двудольного графа с помощью igraph inR

У меня есть данные двухлинейного сетевого края, такие как tmp ниже: tmp <- read.table(text="PersonID CompanyID P1 C000001 P2 C000001 P3 C000001 P4 C000001 P5 C000001 P6 C000002 P7 C000002 P8 C000002 P9 C000003 P10 C000003 P11 C000003 P12 C000003"…
23 апр '13 в 02:24
1 ответ

Ищем алгоритмы: минимальный разрез для получения двудольного графа

Учитывая неориентированный взвешенный граф (или один связанный компонент большего непересекающегося графа), который обычно будет содержать множество нечетных и четных циклов, я ищу алгоритмы для удаления наименьшего возможного числа ребер, необходим…
28 фев '17 в 11:21
1 ответ

Взвешенная бимодальная проекция двудольного графа с сохранением исходных весов

У меня есть большой ( 36k вершин, 50k ребер) взвешенный бимодальный двудольный граф, и я хотел бы создать проекцию, которая не только подсчитывает соседей, как взвешенная реализация по умолчанию, но и суммирует веса на ребрах. Вы можете думать о нем…
03 дек '14 в 06:40
1 ответ

Находится ли нахождение двух разных совершенных соответствий в двудольном графе co-NP?

Сначала несколько определений. Проблема co-NP является проблемой решения, где ответ "НЕТ" может быть проверен за полиномиальное время. Идеальное совпадение в двудольном графе - это набор пар узлов (пара является ребром в графе), где каждый узел встр…
02 май '15 в 19:21