Un gráfico conectado es un gráfico que contiene una ruta entre dos vértices.

Desafío

Cree un circuito [compuerta NAND de 2 entradas] que determine si un gráfico de 4 vértices está conectado.
(Las 2 entradas de una compuerta pueden ser el mismo bit de entrada u otra compuerta).
Salida Verdadero si el gráfico está conectado y falso en caso contrario.

Entrada

Los seis bordes posibles de un gráfico simple con 4 vértices:

[ ₀ e ₁ , ₀ e ₂ , ₁ e ₂ , ₀ e ₃ , ₁ e ₃ , ₂ e ₃ ]

donde _a e _b representa si hay un borde entre los vértices a y b

La conectividad es equivalente a las siguientes condiciones:

• Si menos de 3 entradas son verdaderas, entonces la salida es falsa.

• Si más de 3 entradas son verdaderas, entonces la salida es verdadera.

• Si exactamente 3 entradas son Verdaderas y forman un triángulo, entonces salen Falso.

• De lo contrario, salida True.

La respuesta que usa la menor cantidad de puertas gana. Los empates se romperán por
la profundidad de circuito más baja (longitud de la ruta más larga desde la entrada a la salida).

30 NANDS

En lugar de preguntar cuándo obtenemos un 1, hice la pregunta de cuándo obtenemos un 0. Es mejor preguntarlo de esta manera porque hay menos 0 que 1.

Aquí está la distribución según el número de aristas (sexta fila del triángulo de Pascal)

Edges     0  1  2  3  4  5  6
Frequency 1  6 15 20 15  6  1 (total 64)
Output    0  0  0  *  1  1  1
* = 0 if triangle (4 possibilities) 1 if claw (4 possibilities) 
1 if two opposite edges and one other (12 possibilities)

Al hacer la pregunta de esta manera, obtenemos el siguiente diagrama y expresión

 ___D___
|\     /|
| E   F |
|  \ /  |
A   X   C
|  / \  |
| /   \ |
|/__B__\|

(A|C|D|B)&(A|D|E)&(D|B|E|F)&(C|B|E)&(A|C|E|F)&(D|F|C)&(A|F|B) 

Suponemos que la salida será predeterminada a 1, pero cambiará a 0 en cualquiera de las siguientes condiciones

1.A 0 para tres bordes adyacentes (prueba 3 entradas)

2.A 0 para dos pares de bordes opuestos (prueba 4 entradas)

Los términos anteriores ya están ordenados de la manera que les permitirá agruparse de la siguiente manera. (Por cierto, esta versión de la expresión es rotacionalmente simétrica respecto al vértice AFB).

((A|D)|((C|B)&E))&((B|E)|((D|F)&C))&((C|F)|((A|E)&D))&(A|F|B)    =6 inverters
   1      1  1       1      1  1       1      1  1      1        =10 (7 OR with both inputs inverted, 3 NAND)
      2                 2                 2               2      =8  (4 OR with one input inverted)
                 2                 2                 2           =6  (3 AND) 
                                                        Total    =30

La puntuación para cada &o |se coloca debajo del símbolo y se justifica de la siguiente manera:

Nivel 0: Invertimos en un inversor para cada entrada: 6 NANDS

Nivel 1: Podemos construir un OR a partir de una puerta NAND colocando un inversor en la entrada (un total de 3 NANDS) pero como ya invertimos en 6 NANDS en el paso anterior, podemos hacer 7 puertas OR a partir de 7 puertas NAND. También necesitamos 3 puertas Y. Para estos, solo usaremos NAND y dejaremos la salida invertida. 10 NANDS

Nivel 2: Nuevamente construimos 4 puertas OR a partir de puertas NAND. En cada caso tenemos 1 entrada desde una puerta OR, por lo que tenemos que invertir eso. Pero la otra entrada ya está invertida (proveniente de una de las NAND en el paso anterior que corresponde a un &símbolo en tres casos, y de un inversor en el último), por lo que solo necesitamos 2 puertas para cada funcionalidad OR. 4 * 2 = 8

Nivel 3: ahora necesitamos Y las cuatro salidas juntas. Esto requiere 3 compuertas AND, cada una construida a partir de 2 NAND, 3 * 2 = 6

Eso es un total de 30 puertas NAND, con una profundidad máxima de 2 + 2 + 4 = 8 NAND para ramas con un |nivel 1 o 3 + 1 + 4 = 8 NAND para ramas con un &nivel 1.

El siguiente script de Ruby confirma visualmente que la expresión anterior es válida.

64.times{|i|
  a=i%2
  b=i/2%2
  c=i/4%2
  d=i/8%2
  e=i/16%2 
  f=i/32%2

puts i, ((a|d)|((c|b)&e))&((b|e)|((d|f)&c))&((c|f)|((a|e)&d))&(a|f|b)

puts " ___#{d}___
|\\     /|
| #{e}   #{f} |
|  \\ /  |
#{a}   X   #{c}
|  / \\  |
| /   \\ |
|/__#{b}__\\|


"
}

19 NANDs

No hay un circuito más simple que este.

Hay un código para probarlo debajo de la imagen. En cuanto a entenderlo, eso es difícil. Hay un par de puertas IF allí, y las entradas se agrupan en un triángulo con las líneas de esquina libres agregadas para el análisis una por una, pero no de una manera simple. Si alguien logra entenderlo, quedaré impresionado.

Código Verilog con pruebas:

// 4-vertex Connectedness Tester                                                                  
// Minimal at 19 NANDs                                                                            
//                                                                                                
// By Kim Øyhus 2018 (c) into (CC BY-SA 3.0)                                                      
// This work is licensed under the Creative Commons Attribution 3.0                               
// Unported License. To view a copy of this license, visit                                        
// https://creativecommons.org/licenses/by-sa/3.0/                                                
//                                                                                                
// This is my entry to win this Programming Puzzle & Code Golf                                    
// at Stack Exchange:                                                                             
// /codegolf/69912/build-a-4-vertex-connectedness-tester-using-nand-gates/                                                                                      
//                                                                                                
// I am sure there are no simpler solutions to this problem.                                      
// It has a logical depth of 11, which is deeper than                                             
// circuits using a few more NANDs.                                                               

module counting6 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, out000 );
  input  in_000, in_001, in_002, in_003, in_004, in_005, in_006;
  output out000;
  wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017;

  nand gate000 ( wir000, in_000, in_000 );
  nand gate001 ( wir001, in_001, in_003 );
  nand gate002 ( wir002, wir001, wir000 );
  nand gate003 ( wir003, in_002, wir002 );
  nand gate004 ( wir004, wir002, wir002 );
  nand gate005 ( wir005, wir004, in_002 );
  nand gate006 ( wir006, wir005, wir004 );
  nand gate007 ( wir007, in_005, wir006 );
  nand gate008 ( wir008, in_003, wir006 );    
  nand gate009 ( wir009, in_004, wir003 );
  nand gate010 ( wir010, wir003, wir009 );
  nand gate011 ( wir011, wir009, wir000 );
  nand gate012 ( wir012, wir011, in_001 );
  nand gate013 ( wir013, wir008, wir012 );
  nand gate014 ( wir014, wir013, in_005 );
  nand gate015 ( wir015, wir006, wir013 );
  nand gate016 ( wir016, wir015, wir007 );
  nand gate017 ( wir017, wir016, wir010 );
  nand gate018 ( out000, wir014, wir017 );
endmodule


module connecting6_test;
   reg [5:0] X;
   wire a;

  counting6 U1 (
  .in_000 (X[0]),
  .in_001 (X[1]),
  .in_002 (X[2]),
  .in_003 (X[3]),
  .in_004 (X[4]),
  .in_005 (X[5]),
  .in_006 (X[6]),
  .out000 (a )
  );

  initial begin
    X = 0;
  end

  always
    #10  X = X+1;

 initial  begin
    $display("\t\t     \t_");
    $display("\t\ttime,\t \\db/_,\tconnected");
    $monitor("%d,\t%b,\t%d",$time, X, a );
  end

  initial
   #630  $finish;

endmodule

// iverilog -o hello hello.v                                                                      
// vvp hello                                                                                      

Kim Øyhus

Mathematica, 17 puertas

Simplemente enumeramos todas las reglas, construimos la función booleana y la minimizamos en NANDforma.

#->If[Total@#<3||
       MemberQ[{{1,1,1,0,0,0},{1,0,0,1,1,0},{0,1,0,1,0,1},{0,0,1,0,1,1}},#]
       ,0,1] /.{1->True,0->False}& /@
     Tuples[{0,1},6];
BooleanMinimize[BooleanFunction[rule], "NAND"]

Resultado :

(#1⊼#2⊼#4)⊼(#1⊼#2⊼#5)⊼(#1⊼#2⊼#6)⊼(#1⊼#3⊼#4)⊼ \
(#1⊼#3⊼#5)⊼(#1⊼#3⊼#6)⊼(#1⊼#4⊼#6)⊼(#1⊼#5⊼#6)⊼ \
(#2⊼#3⊼#4)⊼(#2⊼#3⊼#5)⊼(#2⊼#3⊼#6)⊼(#2⊼#4⊼#5)⊼ \
(#2⊼#5⊼#6)⊼(#3⊼#4⊼#5)⊼(#3⊼#4⊼#6)⊼(#4⊼#5⊼#6)&

, donde #1...#6hay 6 espacios para argumentos.

Casos de prueba :

f=%; (* assign the function to symbol f *)

f[True, True, True, True, False, False]
(* True *)

f[True, True, False, True, False, False]
(* True *) (*, three Trues do not form a triangle *)

f[True, True, True, False, False, False]
(* False *) (*, three Trues form a triangle *)

64 NANDs

Los seis bordes se pueden dividir en tres pares de bordes opuestos. Para que se conecte un gráfico, debe haber dos bordes opuestos, así como un tercer borde, o tres bordes conectados al mismo vértice.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Los pares opuestos son UX, VY, WZ, entonces:

A = U+V   ;3 gates
B = W+X
C = Y+Z

D = UV(B+C)  ;2+2+3=7 gates
E = WX(A+C)
F = YZ(C+A)

Result = D+E+F+UVW+UYZ+XVZ+XWY ; 18 + 16 = 34 gates

Construyendo puertas AND y OR de la manera usual, el número total de puertas utilizadas es 3*3+7*3+34= 64.