Est-ce bipartite?

13

Un graphe bipartite est un graphe dont les sommets peuvent être divisés en deux ensembles disjoints, de sorte qu'aucune arête ne relie deux sommets du même ensemble. Un graphique est bipartite si et seulement s'il est bicolore.

Défi

Votre tâche consiste à, étant donné la matrice d'adjacence d'un graphe simple non orienté, déterminer s'il s'agit d'un graphe biparti. Autrement dit, si une arête relie les sommets i et j, les entrées (i, j) et (j, i) de la matrice sont égales à 1.

Le graphe étant non orienté et simple, sa matrice d'adjacence est symétrique et ne contient que 0 et 1.

Détails

Vous devez prendre une matrice N par N en entrée (sous n'importe quelle forme, par exemple liste de listes, liste de chaînes, de type C int**et taille, tableau aplati, entrée brute, etc.).

La fonction / le programme doit retourner / afficher une valeur véridique si le graphique est bipartite, et faux sinon.

Cas de test

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

Notation

Les buildins qui calculent directement la réponse sont interdits.

Il s'agit de code-golf , donc le programme le plus court (en octets) d'ici la fin de ce mois gagne!

code-golf decision-problem graph-theory binary-matrix Colera Su
la source
Lié , et en fait dupe limite, parce qu'être bipartite équivaut à ne pas avoir de cycles impairs, et la plupart des réponses à cette question fonctionnent en énumérant tous les cycles et en examinant leurs longueurs.
Peter Taylor
@PeterTaylor Oui, mais il existe des moyens plus simples de résoudre ce problème.
Colera Su
@ColeraSu Au lieu de vérité / fausse, pouvons-nous retourner -1pour fausse et tout entier non négatif pour vérité?
M. Xcoder
@MishaLavrov 0-> Falsy, >0-> Truthy est généralement autorisé par les règles standard de vérité / fausse. -1et ce ≥ 0n'est pas si courant, c'est pourquoi j'ai demandé.
M. Xcoder
@ Mr.Xcoder C'est bon.
Colera Su

Réponses:

4

Husk , 17 octets

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

Imprime un entier positif si le graphique est biparti, 0sinon. Essayez-le en ligne!

Explication

Il s'agit d'une approche par force brute: parcourez tous les sous-ensembles S des sommets et voyez si toutes les arêtes du graphe sont entre S et son complément.

§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
la source
@ Mr.Xcoder Eh bien, supposons M = [[1,2,3],[4,5,6],[7,8,9]]et S = [1,0,1]( Mest toujours une matrice binaire dans le programme, mais c'est plus facile à expliquer de cette façon). Filtrer chaque ligne de Mpar Sdonne [[1,3],[4,6],[7,9]]: pour chaque ligne, je supprime les éléments à ces indices où Sa un 0. Ensuite, je nie par Sélément pour obtenir [0,1,0], et je filtre Mpar cela pour obtenir [[4,6]]: la première et la dernière ligne ont 0 dans les indices correspondants , ils sont donc supprimés.
Zgarb
17

Wolfram Language (Mathematica) , 26 25 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Étant donné une matrice d'adjacence A, nous trouvons le point fixe de commencer par B = A, puis de remplacer B par A 2 B, écrêtant parfois des valeurs supérieures à 1 à 1. La k ème étape de ce processus est équivalente Clipaux puissances de recherche A 2k + 1 , dans lequel l'entrée (i, j) compte le nombre de chemins de longueur 2k + 1 du sommet i à j; par conséquent, le point fixe finit par avoir une entrée non nulle (i, j) si nous pouvons passer de i à j en un nombre impair d'étapes.

En particulier, la diagonale du point fixe n'a des entrées non nulles que lorsqu'un sommet peut atteindre lui-même un nombre impair d'étapes: s'il y a un cycle impair. La trace du point fixe est donc 0 si et seulement si le graphe est bipartite.

Une autre solution de 25 octets de ce formulaire est Tr[#O@n//.x_:>#.#.x]===0&, au cas où cela donnerait à quelqu'un des idées sur la façon de pousser le nombre d'octets encore plus bas.

Efforts antérieurs

J'ai essayé un certain nombre d'approches de cette réponse avant de m'installer sur celle-ci.

26 octets: exponentielles matricielles

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

S'appuie également sur les puissances impaires de la matrice d'adjacence. Puisque x * exp (x 2 ) est x + x 3 + x 5/2 ! + x 7/4 ! + ..., lorsque x est une matrice A, cela a un terme positif pour chaque puissance impaire de A, donc il aura également une trace nulle si A a un cycle impair. Cette solution est très lente pour les grandes matrices.

29 octets: grande puissance impaire

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

Pour une matrice n par n A, trouve A 2n + 1 puis effectue la vérification diagonale. Ici, #~Table~Tr[2#!]génère 2n copies de la matrice d'entrée n par n et #.##& @@ {a,b,c,d}déballe a.a.b.c.d, multipliant ainsi 2n + 1 copies de la matrice.

53 octets: matrice laplacienne

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

Utilise un résultat obscur dans la théorie des graphes spectraux ( proposition 1.3.10 dans ce pdf ).

Misha Lavrov
la source
Je pense que vous pouvez raser quelques octets de votre méthode plus efficace avec Tr[#.Nest[#.#&,#,Tr[#!]]]<1&. (C'est une réponse incroyable qui ne cesse de s'améliorer à chaque fois que je la regarde!)
Pas un arbre
1
Cela a moins d'octets que le semi-intégré (a besoin de deux fonctions)BipartiteGraphQ@AdjacencyGraph@#&
Kelly Lowder
2
@KellyLowder: pour les grandes matrices MatrixExprenvoie des résultats en termes d' Rootobjets non évalués , qui ne sont pas automatiquement simplifiés lorsqu'ils sont ajoutés. Les N@forces Rootdoivent être calculées numériquement pour que la véracité puisse ensuite être évaluée.
Michael Seifert
1
@Notatree Votre approche rase en effet quelques octets, mais ils coûtent; pour les matrices 18x18, c'est 1000 fois plus lent, et ça empire à partir de là. Je pense que si je fais ce changement, je perds le droit d'appeler la méthode efficace "efficace".
Misha Lavrov
1
@KellyLowder Vous pouvez raccourcir cela BipartiteGraphQ@*AdjacencyGraph, mais c'est encore plus long.
Martin Ender
3

JavaScript, 78 octets

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

Tableau d'entrée du tableau de 0/1, sortie vrai / faux.

Afficher l'extrait de code

tsh
la source
2

Pyth , 25 octets

xmyss.D.DRx0dQx1d.nM*FQss

Essayez-le en ligne!

Cela renvoie -1pour la fausse, et tout entier non négatif pour la vérité.

Comment ça fonctionne

xmyss.D.DRx0dQx1d.nM * FQss ~ Programme complet, reçoit une matrice d'adjacence de STDIN.

                    * FQ ~ Réduire (plier) par produit cartésien.
                 .nM ~ Aplatir chacun.
 m ~ Carte avec une variable d.
         RQ ~ Pour chaque élément de l'entrée,
       .D ~ Supprimer les éléments aux index ...
          x0d ~ Tous les index de 0 en d.
     .D ~ Et de cette liste, supprimez les éléments des index ...
              x1d ~ Tous les index de 1 en d.
    s ~ Aplatir.
   s ~ Sum. J'aurais pu utiliser s si [] n'apparaissait pas.
  y ~ Double.
x ~ Dans le mappage ci-dessus, obtenez le premier index de ...
                       ss ~ Le nombre total de 1 dans la matrice d'entrée.

Cela fonctionne dans commit d315e19 , la version actuelle de Pyth que TiO a.

M. Xcoder
la source