Niech G będzie grafem rzędu n = 2 , w którym wierzchołki są 8 wyznaczone przez p Karmel: Niech G będzie grafem rzędu n = 28 , w którym wierzchołki są wyznaczone przez parami różne ciągi binarne długości 8. Dwa wierzchołki są połączone krawędzią wtedy i tylko wtedy, gdy w odpowiadających im ciągach ilości jedynek różnią się o jeden. Jaka jest minimalna liczba krawędzi, które muszą zostać usunięte z G w celu uzyskania grafu Eulera?
13 lut 16:49
Pytający: Niech G = (V, E), Vk = {v ∊ V: "v jest wyznaczony przez ciąg z dokładnie k jedynkami"}. Wtedy:
 
nawias
8
nawias
nawias
k
nawias
 
|Vk| =
  
 
nawias
8
nawias
nawias
1
nawias
 
v ∊ V0 deg(v) =
  
 
nawias
8
nawias
nawias
k − 1
nawias
nawias
8
nawias
nawias
k + 1
nawias
 
k ∊ {1, 2, 3, 4, 5, 6, 7}v ∊ Vk deg(v) =
  
 
nawias
8
nawias
nawias
7
nawias
 
v ∊ V8 deg(v) =
  
Jedyne wierzchołki o stopniach nieparzystych to te należące do V1 i V7. Wystarczy usunąć krawędzie łączące je odpowiednio z V0 i V8. Czyli trzeba usunąć 2 * 8 = 16 krawędzi. A jest to minimalna liczba krawędzi, które trzeba usunąć, bo żadne dwa wierzchołki o stopniach nieparzystych nie są ze sobą połączone krawędzią w pierwotnym grafie, więc trzeba usunąć co najmniej tyle krawędzi, ile jest takich wierzchołków, tj. |V1| + |V7| = 16.
13 lut 20:57