Función: Grafo BipartitoVolver

Descripción

Comprueba si un grafo es bipartito, y si lo es, devuelve los dos conjuntos disjuntos U y V, en caso contrario nulo

https://cp-algorithms.com/graph/bipartite-check.html

Cadena de entrada

gr_bipartito

Cadena de salida

GRAFO.bipartito

Uso

gr_bipartito(<grafo>)

Ejemplos



Grafo no dirigido de 5 nodos:

gr_nuevo([[0,0,0,1,0],[0,0,0,1,0],[0,0,0,0,1],[1,1,0,0,0],[0,0,1,0,0]],falso)

Salida JMEScriptGUI con visor de grafos v0.1:


Comprobar si el grafo anterior es bipartito:

gr_bipartito(gr_nuevo([[0,0,0,1,0],[0,0,0,1,0],[0,0,0,0,1],[1,1,0,0,0],[0,0,1,0,0]],falso))

VectorEvaluado: [[0,1,2],[3,4]]

Comprobar si el grafo anterior es bipartito completo:

Salida en REPL:

>>> set g=gr_nuevo([[0,0,0,1,0],[0,0,0,1,0],[0,0,0,0,1],[1,1,0,0,0],[0,0,1,0,0]],falso)|| >>> set particion=gr_bipartito(g) particion ==> VectorEvaluado: [[0,1,2],[3,4]] (parse: 112µs(8%) / eval: 1,2ms(92%) / total: 1,3ms) >>> dim(particion><0)*dim(particion><1)=gr_numaristas(g) ==> Booleano: falso (parse: 993µs(45%) / eval: 1,2ms(55%) / total: 2,2ms) >>>



K3,2:

gr_nuevo([[0,0,0,1,1],[0,0,0,1,1],[0,0,0,1,1],[1,1,1,0,0],[1,1,1,0,0]],falso)

Salida JMEScriptGUI con visor de grafos v0.1:


Comprobar si el grafo anterior es bipartito:

gr_bipartito(gr_nuevo([[0,0,0,1,1],[0,0,0,1,1],[0,0,0,1,1],[1,1,1,0,0],[1,1,1,0,0]],falso))

VectorEvaluado: [[0,1,2],[3,4]]

Comprobar si el grafo anterior es bipartito completo:

Salida en REPL:

>>> set k32=gr_nuevo([[0,0,0,1,1],[0,0,0,1,1],[0,0,0,1,1],[1,1,1,0,0],[1,1,1,0,0]],falso)|| >>> set particion=gr_bipartito(k32) particion ==> VectorEvaluado: [[0,1,2],[3,4]] (parse: 71,5µs(9%) / eval: 686µs(91%) / total: 758µs) >>> dim(particion><0)*dim(particion><1)=gr_numaristas(k32) ==> Booleano: verdadero (parse: 345µs(30%) / eval: 794µs(70%) / total: 1,1ms) >>>



K20:

gr_nuevo(const(const(1,20),20)-mat1(20),falso)

Salida JMEScriptGUI con visor de grafos v0.1:


Comprobar si el grafo anterior es bipartito:

gr_bipartito(gr_nuevo(const(const(1,20),20)-mat1(20),falso))

Texto: '__null__'

Desde / Última modificación

v0.6.2.0