Anmerkungen und Erläuterungen


 

Erläuterungen zur Mächtigkeit:

Bekanntlich ist die Mächtigkeit einer Graph-Familie (Beginn Knoten-Nr.1) = (n-1) !
Hat man nur jede zweite Kante, ohne die Richtung und die Reihenfolge ändern zu können,
dann ist hier die Mächtigkeit der Teilgraph-Familie ebenfalls (n-1)!, weil implizit die fehlenden
Kanten festgelegt bleiben:

u(xi,xj)m => u(xj,xk)m+1
Aus der Kante um mit dem End-Knoten xj  bestimmt sich der Anfangs-Knoten xj der Folgekante um+1

u(xi,xj)m und u(xk,xl)m+2  =>  u(xj,xk)m+1
Ist eine Kante und die übernächste Kante bekannt, so ist auch die eingeschlossene Kante bekannt..

um, um+2, um+4, um+6, ...  =>  um+1, um+3, um+5 , ....
Aus dem Teilgraph, der nur jede zweite Kante des Gesamt-Graphen enthält , ergeben sich implizit die fehlenden Kanten des Gesamtgraphen.

  => | TG | = | G |  , bei fester Vorgabe der Kantenreihenfolge und der Richtung der Kanten im Teilgraph.


Weitere  Überlegungen:

Definitionen:

TG{ ua,ub,uc,ud,ue, ... }  
TGPi  = Permutaion von TG 
f(TG) = å (ua,ub,uc,ud,ue, ...)

=> TG ¹ TGPi   ; aber: f(TG) = f(TGPi)
Jede Permatution eines Teilgraphen ist ungleich zum Teilgraphen natürlicher Reihenfolge. Nach dem Kommutativ-Gesetz ist jedoch die Summe der Kantenlängen als Funktion des Teilgraphen gleich der Summe der Kantenlängen jeder beliebigen Permutation.

 

Weiter gilt bei Symmetrie:

f(u(xi,xj)) = f(u’(xj,xi))
Bei Symmetrie ist der Funktionswert einer Kante gleich dem Funktionswert der Kante in Gegenrichtung.

f(TG) = å (ua, ...)  º  f(TG’) = å (u’a, ...)
Daraus folgt, dass jede Kante gegen ihre „Gegen“-Kante ausgetauscht werden kann, ohne dass sich der Funktionswert des Teilgraphen ändert. Ist daher der Funktionswert des TG mit der natürlichen Reihenfolge seiner Kanten bestimmt, so ist damit der TG-Funktionswert aller Permutationen und Variationen von Kanten mit Gegen-Kanten bestimmt und muß nicht mehr berechnet werden.

Die Berechnungen aller (n/2-1)! * 2(n/2-1) TG fällt zu einer einzigen Berechnung zusammen.  


 

Formel für die Mächtigkeit der Teilgraphfamilie (bei Symmetrie):

Beispiel: n = 10
            
1   x   3   x   5   x   7   x   9  =
            
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9   
————————————————— =
    2   x   4   x   6   x   8            
                
               (n-1)! 
————————————————— =
  (1x2) x (2x2) x (3x2) x (4x2)            
            
               (n-1)! 
————————————————— =
    (1x2x3x4)    x   (2x2x2x2)        
 
               (n-1)!                            n!
—————————————————  —————————————————
    (n/2 -1)!    x   2**(n/2 -1)        (n/2)!   x    2**(n/2)  
      
   

1. Die Fakultät im Nenner drückt die Permutation der (n/2)-1 freien Kanten aus.
2. Die 2er-Potenz drückt die Variation bei Symmetrie jeder freien Kante u(ij) mit der "Gegen-"Kante u(ji) aus. 
3. Besteht keine Symmetrie wird die 2er-Potenz zu 20 = 1.

Der gesamte Nenner drückt die Anzahl der Komplement-Teilgraphen je Teilgraph aus.

|TG|  x  |TGKomp|  = (n-1)!
Die Mächtigkeit der Teilgraphen multipliziert mit der Mächtigkeit der Komplement-Teilgraphen 
ergibt die Mächtigkeit des Gesamtgraphen bzw. bei Symmetrie das Zweifache davon, weil je
zwei Gesamtgraphen doppelt vorkommen.