Ist es zweiteilig?

13

Ein zweigeteiltes Diagramm ist ein Diagramm, dessen Scheitelpunkte in zwei nicht zusammenhängende Gruppen unterteilt werden können, sodass keine Kante zwei Scheitelpunkte in derselben Gruppe verbindet. Ein Graph ist genau dann zweiteilig, wenn er zweifarbig ist.

Herausforderung

Ihre Aufgabe ist es, anhand der Adjazenzmatrix eines ungerichteten einfachen Diagramms zu bestimmen, ob es sich um ein zweigliedriges Diagramm handelt. Das heißt, wenn eine Kante die Eckpunkte i und j verbindet, sind sowohl der (i, j) als auch der (j, i) Eintrag der Matrix 1.

Da der Graph ungerichtet und einfach ist, ist seine Adjazenzmatrix symmetrisch und enthält nur 0 und 1.

Besonderheiten

Sie sollten eine N-mal-N-Matrix als Eingabe verwenden (in beliebiger Form, z. B. Liste der Listen, Liste der Zeichenfolgen, C-ähnlich int**und Größe, abgeflachtes Array, unformatierte Eingabe usw.).

Die Funktion / das Programm sollte einen Wahrheitswert zurückgeben / ausgeben, wenn der Graph zweiteilig ist, und ansonsten falsch.

Testfälle

['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

Wertung

Builtins, die die Antwort direkt berechnen, sind gesperrt.

Das ist Code-Golf , also gewinnt das kürzeste Programm (in Bytes) bis Ende dieses Monats!

code-golf decision-problem graph-theory binary-matrix Colera Su
quelle
Verwandte , und in der Tat Borderline-Dupe, weil zweiteilig zu sein gleichbedeutend ist, keine ungeraden Zyklen zu haben, und die meisten Antworten auf diese Frage funktionieren, indem alle Zyklen aufgezählt und ihre Länge untersucht werden.
Peter Taylor
@ PeterTaylor Ja, aber es gibt einfachere Möglichkeiten, um dieses Problem zu lösen.
Colera So
@ColeraSu Können wir anstelle von Wahr / Falsch -1für Falsch und für Wahr eine nicht negative ganze Zahl zurückgeben?
Mr. Xcoder
@MishaLavrov 0-> Falsy, >0-> Truthy wird im Allgemeinen durch Standardregeln für Wahrheiten / Falschheiten zugelassen. -1und ≥ 0ist nicht so verbreitet, deshalb habe ich gefragt.
Mr. Xcoder
@ Mr.Xcoder Ist schon okay.
Colera So

Antworten:

4

Schale , 17 Bytes

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

Gibt eine positive Ganzzahl aus, wenn das Diagramm zweigeteilt ist 0. Probieren Sie es online!

Erläuterung

Dies ist ein Brute-Force-Ansatz: Durchlaufen Sie alle Untergruppen S von Scheitelpunkten und prüfen Sie, ob alle Kanten im Diagramm zwischen S und seinem Komplement liegen.

§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
quelle
@ Mr.Xcoder Naja, angenommen M = [[1,2,3],[4,5,6],[7,8,9]]und S = [1,0,1]( Mist immer eine binäre Matrix im Programm, aber es ist einfacher, dies so zu erklären). Das Filtern jeder Zeile Mnach Sergibt [[1,3],[4,6],[7,9]]: Für jede Zeile entferne ich die Elemente an den Indizes, an denen Seine 0 vorhanden ist. Dann negiere ich die zu erhaltenden SElemente [0,1,0]und filtere danach M, um zu erhalten [[4,6]]: Die erste und die letzte Zeile haben 0 in den entsprechenden Indizes Also werden sie entfernt.
Zgarb,
17

Wolfram-Sprache (Mathematica) , 26 25 Bytes

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

Probieren Sie es online!

Wie es funktioniert

Bei gegebener Adjazenzmatrix A finden wir den Fixpunkt, bei dem wir mit B = A beginnen und dann B durch A 2 B ersetzen. Dabei werden gelegentlich Werte größer als 1 bis 1 abgeschnitten. Der k- te Schritt dieses Prozesses entspricht der ClipErmittlung von Potenzen A 2k + 1 , in dem der Eintrag (i, j) die Anzahl der Pfade der Länge 2k + 1 vom Scheitelpunkt i bis j zählt; Daher hat der feste Punkt einen Eintrag ungleich Null (i, j), wenn wir in einer ungeraden Anzahl von Schritten von i nach j gehen können.

Insbesondere hat die Diagonale des Fixpunkts nur dann Einträge ungleich Null, wenn sich ein Eckpunkt in einer ungeraden Anzahl von Schritten selbst erreichen kann: wenn es einen ungeraden Zyklus gibt. Die Kurve des Fixpunkts ist also genau dann 0, wenn der Graph zweiteilig ist.

Eine andere 25-Byte-Lösung dieser Form ist Tr[#O@n//.x_:>#.#.x]===0&, falls dies jemandem Ideen darüber gibt, wie die Byteanzahl noch weiter gesenkt werden kann.

Frühere Bemühungen

Ich habe eine Reihe von Ansätzen für diese Antwort ausprobiert, bevor ich mich für diese entschieden habe.

26 Bytes: Matrixexponentiale

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

Beruht auch auf ungeraden Potenzen der Adjazenzmatrix. Da x * exp (x 2 ) x + x 3 + x 5/2 ist ! + x 7/4 ! + ..., wenn x eine Matrix A ist, hat dies einen positiven Term für jede ungerade Potenz von A, so dass es auch eine Nullspur gibt, wenn A einen ungeraden Zyklus hat. Diese Lösung ist für große Matrizen sehr langsam.

29 Bytes: große ungerade Leistung

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

Findet für eine n mal n-Matrix A A 2n + 1 und führt dann die Diagonalenprüfung durch. Hier werden #~Table~Tr[2#!]2n Kopien der Eingangsmatrix n #.##& @@ {a,b,c,d}x n generiert und entpackt, wodurch a.a.b.c.d2n + 1 Kopien der Matrix multipliziert werden.

53 Bytes: Laplace-Matrix

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

Verwendet ein obskures Ergebnis in der Spektralgraphentheorie ( Proposition 1.3.10 in diesem PDF ).

Mischa Lawrow
quelle
Ich denke, Sie können ein paar Bytes Ihrer effizienteren Methode mit rasieren Tr[#.Nest[#.#&,#,Tr[#!]]]<1&. (Dies ist eine unglaubliche Antwort, die von Mal zu Mal besser wird!)
Kein Baum
1
Dies hat weniger Bytes, die das Semi- BipartiteGraphQ@AdjacencyGraph@#&
Kelly Lowder
2
@KellyLowder: Bei großen Matrizen werden MatrixExpErgebnisse in Form von nicht bewerteten RootObjekten zurückgegeben, die beim Hinzufügen nicht automatisch vereinfacht werden. Das N@zwingt dazu, diese Rootnumerisch zu berechnen, damit dann die Wahrhaftigkeit bewertet werden kann.
Michael Seifert
1
@Notatree Dein Ansatz spart zwar ein paar Bytes, aber sie kosten; Für 18x18-Matrizen ist es 1000-mal langsamer und wird von da an schlimmer. Ich denke, wenn ich diese Änderung vornehme, verliere ich das Recht, die effiziente Methode "effizient" zu nennen.
Mischa Lawrow
1
@ KellyLowder Du könntest das auf kürzen BipartiteGraphQ@*AdjacencyGraph, aber es ist noch länger.
Martin Ender
3

JavaScript, 78 Byte

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

Eingabearray des Arrays von 0/1, Ausgabe wahr / falsch.

Code-Snippet anzeigen

tsh
quelle
2

Pyth , 25 Bytes

xmyss.D.DRx0dQx1d.nM*FQss

Probieren Sie es online!

Dies -1ergibt eine falsche Zahl und eine nicht negative ganze Zahl für die Wahrheit.

Wie es funktioniert

xmyss.D.DRx0dQx1d.nM * FQss ~ Vollständiges Programm, erhält eine Adjazenzmatrix von STDIN.

                    * FQ ~ Nach kartesischem Produkt reduzieren (falten).
                 .nM ~ Jeweils abflachen.
 m ~ Karte mit einer Variablen d.
         RQ ~ Für jedes Element in der Eingabe
       .D ~ Löschen Sie die Elemente an den Indizes ...
          x0d ~ Alle Indizes von 0 in d.
     .D ~ Und aus dieser Liste löschen Sie die Elemente an den Indizes ...
              x1d ~ Alle Indizes von 1 in d.
    s ~ Abflachen.
   s ~ Summe. Ich hätte s benutzen können, wenn [] nicht aufgetaucht wäre.
  y ~ Double.
x ~ In der obigen Abbildung erhalten Sie den ersten Index von ...
                       ss ~ Die Gesamtzahl der Einsen in der Eingabematrix.

Dies funktioniert in commit d315e19 , der aktuellen Pyth-Version von TiO.

Mr. Xcoder
quelle