Это двудольный?

13

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

Вызов

Ваша задача состоит в том, чтобы, учитывая матрицу смежности неориентированного простого графа, определить, является ли он двудольным графом. То есть, если ребро соединяет вершины i и j, оба элемента (i, j) и (j, i) матрицы равны 1.

Поскольку граф является ненаправленным и простым, его матрица смежности симметрична и содержит только 0 и 1.

конкретика

Вы должны использовать матрицу N-N-N в качестве входных данных (в любой форме, например, список списков, список строк, C-подобный int**и размер, плоский массив, необработанный ввод и т. Д.).

Функция / программа должна возвращать / выводить истинное значение, если график является двудольным, и ложным в противном случае.

Тестовые случаи

['00101',
 '00010',
 '10001',
 '01000',
 '10100'] : False
['010100',
 '100011',
 '000100',
 '101000',
 '010000',
 '010000'] : True (divide into {0, 2, 4, 5} and {1, 3})
['00',
 '00'] : True

счет

Встроенные функции, которые вычисляют ответ напрямую, запрещены.

Это код-гольф , поэтому выигрывает самая короткая программа (в байтах) к концу этого месяца!

code-golf decision-problem graph-theory binary-matrix Колера Су
источник
Связанный , и фактически пограничный обман, потому что быть двудольным эквивалентно отсутствию нечетных циклов, и большинство ответов на этот вопрос работают, перечисляя все циклы и исследуя их длины.
Питер Тейлор
@PeterTaylor Да, но есть более простые способы решить эту проблему.
Колера Су
@ColeraSu Вместо правды / ложи, можем ли мы вернуться -1за ложь и любое неотрицательное целое число для правды?
г-н Xcoder
@MishaLavrov 0-> Falsy, >0-> Truthy, как правило, допускается стандартными правилами true / falsy. -1и ≥ 0это не так часто, поэтому я и спросил.
г-н Xcoder
@ Mr.Xcoder Все в порядке.
Колера Су

Ответы:

4

Шелуха , 17 байт

§V¤=ṁΣṠMSȯDfm¬ṀfΠ

Печатает положительное целое число, если график является двудольным, 0если нет. Попробуйте онлайн!

объяснение

Это подход грубой силы: переберите все подмножества S вершин и посмотрите, все ли ребра графа находятся между S и его дополнением.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
                Π  Cartesian product; result is X.
                   Elements of X are binary lists representing subsets of vertices.
                   If M contains an all-0 row, the corresponding vertex is never chosen,
                   but it is irrelevant anyway, since it has no neighbors.
                   All-1 rows do not occur, as the graph is simple.
      ṠM           For each list S in X:
              Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
        S  fm¬     then filter the result by the element-wise negation of S,
         ȯD        and concatenate the resulting matrix to itself.
                   Now we have, for each subset S, a matrix containing the edges
                   from S to its complement, twice.
§V                 1-based index of the first matrix
  ¤=               that equals M
    ṁΣ             by the sum of all rows, i.e. total number of 1s.
                   Implicitly print.
Zgarb
источник
@ Mr.Xcoder Ну, предположим, M = [[1,2,3],[4,5,6],[7,8,9]]и S = [1,0,1]( Mэто всегда двоичная матрица в программе, но так проще объяснить). Фильтрация каждого ряда Mпо Sдает [[1,3],[4,6],[7,9]]: для каждой строки, я удаляю на этих индексах элементов , где Sесть 0. Тогда я отрицаю Sпоэлементно , чтобы получить [0,1,0], и фильтр Mтем , чтобы получить [[4,6]]: первые и последние строки имеет 0 в соответствующих индексах поэтому они удалены.
Згарб
17

Wolfram Language (Mathematica) , 26 25 байт

Tr[#//.x_:>#.#.Clip@x]<1&

Попробуйте онлайн!

Как это устроено

Учитывая матрицу смежности A, мы находим фиксированную точку, начиная с B = A, а затем заменяя B на A 2 B, изредка обрезая значения, превышающие 1 к 1. k- й шаг этого процесса эквивалентен с точностью Clipдо нахождения степеней 2k + 1 , в которой (I, J) входа подсчитывает число путей длины 2k + 1 от вершины я J; поэтому фиксированная точка имеет ненулевую (i, j) запись, если мы можем перейти от i к j за нечетное количество шагов.

В частности, диагональ неподвижной точки имеет ненулевые элементы, только когда вершина может достичь себя за нечетное количество шагов: если существует нечетный цикл. Таким образом, след неподвижной точки равен 0 тогда и только тогда, когда график является двудольным.

Другое 25-байтовое решение этой формы заключается Tr[#O@n//.x_:>#.#.x]===0&в том, чтобы дать кому-нибудь представление о том, как увеличить количество байтов еще ниже.

Предыдущие усилия

Я попробовал несколько подходов к этому ответу, прежде чем остановиться на этом.

26 байтов: матричные экспоненты

N@Tr[#.MatrixExp[#.#]]==0&

Также полагается на нечетные степени матрицы смежности. Поскольку x * exp (x 2 ) есть x + x 3 + x 5/2 ! + х 7/4 ! + ..., когда x является матрицей A, она имеет положительный член для каждой нечетной степени A, поэтому она также будет иметь нулевой след, если A имеет нечетный цикл. Это решение очень медленно для больших матриц.

29 байт: большая нечетная мощность

Tr[#.##&@@#~Table~Tr[2#!]]<1&

Для матрицы n по n A находит 2n + 1 и затем проверяет диагональ. Здесь #~Table~Tr[2#!]генерируется 2n копий входной матрицы n by n и #.##& @@ {a,b,c,d}распаковывается a.a.b.c.d, умножая в результате 2n + 1 копии матрицы.

53 байта: матрица Лапласа

(e=Eigenvalues)[(d=DiagonalMatrix[Tr/@#])+#]==e[d-#]&

Использует неясный результат в теории спектральных графов ( предложение 1.3.10 в этом pdf ).

Миша лавров
источник
Я думаю, что вы можете сэкономить пару байтов от вашего более эффективного метода Tr[#.Nest[#.#&,#,Tr[#!]]]<1&. (Это невероятный ответ, который становится все лучше с каждым разом, когда я на него смотрю!)
Не дерево
1
Это имеет меньше байтов, чем полу-встроенный (нужно две функции)BipartiteGraphQ@AdjacencyGraph@#&
Келли Лоудер
2
@KellyLowder: для больших матриц MatrixExpвозвращает результаты в терминах неоцененных Rootобъектов, которые автоматически не упрощаются при добавлении. Эти N@силы Rootдолжны быть рассчитаны численно, чтобы затем можно было оценить их достоверность.
Майкл Сейферт
1
@Notatree Ваш подход действительно сбрасывает несколько байтов, но они стоят; для матриц 18x18 это в 1000 раз медленнее, и от этого становится хуже. Я думаю, что если я сделаю это изменение, я потеряю право называть эффективный метод «эффективным».
Миша Лавров
1
@KellyLowder Вы можете сократить это до BipartiteGraphQ@*AdjacencyGraph, но это еще дольше.
Мартин Эндер
3

JavaScript, 78 байт

m=>!m.some((l,i)=>m.some((_,s)=>(l=m.map(t=>t.some((c,o)=>c&&l[o])))[i]&&s%2))

Входной массив массива 0/1, вывод true / false.

Показать фрагмент кода

ТТГ
источник
2

Pyth , 25 байт

xmyss.D.DRx0dQx1d.nM*FQss

Попробуйте онлайн!

Это возвращает -1ложь и любое неотрицательное целое число для правдивости.

Как это устроено

xmyss.D.DRx0dQx1d.nM * FQss ~ Полная программа, получает матрицу смежности от STDIN.

                    * FQ ~ Уменьшить (сложить) декартовым произведением.
                 .nM ~ Свести каждый.
 m ~ Карта с переменной d.
         RQ ~ Для каждого элемента на входе,
       .D ~ Удалить элементы по индексам ...
          x0d ~ Все индексы 0 в d.
     .D ~ И из этого списка удалить элементы по индексам ...
              x1d ~ Все индексы 1 в d.
    S ~ Flatten.
   сумма Я мог бы использовать s, если [] не появится.
  у ~ двойной.
x ~ В приведенном выше отображении получить первый индекс ...
                       ss ~ Общее количество единиц во входной матрице.

Это работает в коммите d315e19 , текущая версия PyO от TiO.

Мистер Xcoder
источник