Graphentheorie: Algorithmus für Gesamt-Anzahl der Subgraphen in Multigraph, z.B. chemisches Molekül ( in C++ ) ??

Hallo liebe Mathematiker,

ich schreibe gerade ein C++ Programm welches chemische Synthesewege/ Reaktionen berechnet. Dazu muß ich die strukturelle Komplexität eines Moleküls bewerten können.
Ich speichere das Melekül in C++ als einen ungerichteten verbundenen Multigraphen
$G ( V, E )$ aus ( nach Atomtyp gefärbten ) "Atomen"=Vertices V und "Bindungen"=Kanten E im Sinne von

[code]

class Atom
{
  int typ;
  list <Bindung*> kanten; // Bindungen zu Nachbaratomen = Kanten im Graph
};

class Bindung
{
  Atom* atom1;
  Atom* atom2;
  int order; // Einfach-, Zweifach- etc. Bindung
};

class Graph
{
  list<Atom>    alist;
  list<Bindung> blist;
  // ...
}; 
[/code]

Ich suche einen Algorithmus, der für diesen Multigraphen die Gesamt-Anzahl der
Subgraphen $N_s$ ausgibt und wenn möglich auch die Anzahl der verschiedenen Subgraphen $N_t$ .

Dieses Problem scheint für große Graphen sehr komplex zu werden
Zum Beispiel gibt es für das Molekül Ethen bereits :

H  --- C === C --- H
        |     |
        H     H

4 * "H" + 2 * "C" + 4 * "H---C" + 4* "C---H" + 2 * "C===C"
+ 2 * "H---C===C" + 2 * "C===C---H" + 4* "H---C---H" +
4 * "H --- CH===C " etc.

Kennt jemand von Euch einen Algorithmus zur Berechnung von $N_s$ und $N_t$ für Graphen $G ( V, E )$ dieser Art?
Am liebsten in C++, aber Pseudocode oder eine andere Programmiersprache oder ein gutes Buch mit einer Beschreibung dieses Algorithmus ist auch OK.

Vielen Dank im Voraus,
L. M.

P.S. Ich bin Chemiker und kein Mathematiker, also Verzeihung wenn das eine dumme Frage war ...

Maxi

Hi!

nur mal so ne idee:

Du könntest versuchen, von jedem Atom alle möglichen Bindungen rauszufinden, und wenns doppelte sind, kann man die ja auch erst später zusammenfassen. Das ganze ginge zB rekursiv:

FindePfad(Atom* a, list<Atom*> Pfad)
{
// Hier kannst du dann das übergebene Atom in ÜPfad eintragen
, und für jedes weitere Atom, welches an a angrenzt wiederum FindePfad
aufrufen. Du musst dir dann noch überlegen, wie du den aktuellen Pfad 
am besten speichern kannst, aber so könnte es gehen

 für jedes Atom
     FindePfad(a->angrenzend, Pfad);
}