Graphentheorie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:08 Di 25.10.2011 | | Autor: | Fry |
Hallo zusammen,
also es geht um Multigraphen [mm] $\Gamma$ [/mm] auf [mm] $\{1,...,N\}$ (N\in\IN)
[/mm]
mit folgenden Eigenschaften:
(1) Jeder Graph [mm] $\Gamma$ [/mm] ist Vereinigung von $n$ Kreisen (der Maximallänge k)
(2) Jeder Graph [mm] $\Gamma$ [/mm] ist keine disjunkte Vereinigung von Doppelkreisen
(im Original "non-intersecting double loops") (der Maximallänge k)
Wie würdet ihr das verstehen, hab mal dazu ein Bildchen gemalt.
[Dateianhang nicht öffentlich]
Eher Variante B,also dass die Kreise einen Knoten gemeinsam haben dürfen oder Variante A, dass sie keine Knoten und Ecken gemeinsam haben dürfen?
(3) Jeder Graph [mm] $\Gamma$ [/mm] besitzt kein Einzelecken (single bonds)
Im folgenden soll nun mit [mm] $n_i$ [/mm] die Multiplizität des Knoten $i$ ($i=1,...,N$),
mit [mm] $n_{ij}$ [/mm] ($i<j,i,j=1,...,N$)die Mulitplizität der Ecke [mm] $\{i,j\}$,$|\Gamma|$ [/mm] die Multiplizität des Graphen [mm] $\Gamma$,d.h.$|\Gamma|=\sum_{i
Nun soll gelten (was ich nicht verstehe):
(4) [mm] $|\Gamma|\le [/mm] n*k$
(5) Für jede Ecke mit [mm] $n_{ij}\not=0$ [/mm] gilt: [mm] $2\le n_{ij}\le [/mm] n$
(6) Für jeden Knoten mit [mm] $n_i\not=0$ [/mm] gilt: [mm] $n_i\ge [/mm] 4$
(7) Es gibt entweder einen Knoten mit [mm] $n_i\ge [/mm] 8$ oder ein Knotenpaar, wobei jeder Knoten [mm] $n_i\ge [/mm] 6$ hat.
Hat jemand eine Ahnung, wie man dies aus (1)-(3) folgern kann?
Bräuchte da dringend eure Hilfe. Bin für jeden Hinweis dankbar.
Lieben Gruß
Fry
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:17 Di 25.10.2011 | | Autor: | Fry |
So, nochmal ein paar Fehler im Text beseitigt und die Zeichnung korrigiert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:30 Di 25.10.2011 | | Autor: | Fry |
Multiplizität eines Knoten = Anzahl der Ecken, die von dem Knoten ausgehen.
Multiplizität der Ecke i,j = Anzahl der Ecken zwischen dem Knoten i und j
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:44 Mi 02.11.2011 | | Autor: | Fry |
Hat niemand eine Idee ? :/
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:23 Mi 09.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
