Graphen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:44 Sa 02.06.2012 | | Autor: | Fry |
Hallo :),
ich habe einen Multigraphen G (ohne Schleifen) mit Knotenmenge [mm] $V\subset\{1,...,N\}$ [/mm] gegeben mit den Eigenschaften
(1) [mm] $d(i)\ge [/mm] 4$, falls $d(i)>0$ und [mm] $i\in [/mm] V$
(2) Ferner existiere entweder ein [mm] $i\in [/mm] V$ mit [mm] $d(i)\ge [/mm] 8$
oder es existieren zwei verschiedene Knoten $i,j$ mit [mm] $d(i),d(j)\ge [/mm] 6$.
(d(i) sei der Grad des Knoten i)
Daraus soll folgen, dass [mm] $|E|\ge [/mm] 2|V|+2$,wobei
$|E|$= Anzahl der Kanten von G (mit Vielfachheit gezählt)
$|V|$= Anzahl der Knoten von G
Ich weiß, dass [mm] $|E|=\frac{1}{2}\sum_{i\in V}d(i)$. [/mm] Aber weiter komm ich nicht. Muss wohl relativ trivial sein. Aber seh ich nicht, wie man auf die Abschätzung kommt.
Könnte mir jemand bitte einen Hinweis geben?
Danke!
VG
Fry
|
|
| |
|
> Hallo :),
>
> ich habe einen Multigraphen G (ohne Schleifen) mit
> Knotenmenge [mm]V\subset\{1,...,N\}[/mm] gegeben mit den
> Eigenschaften
> (1) [mm]d(i)\ge 4[/mm], falls [mm]d(i)>0[/mm] und [mm]i\in V[/mm]
> (2) Ferner
> existiere entweder ein [mm]i\in V[/mm] mit [mm]d(i)\ge 8[/mm]
> oder es
> existieren zwei verschiedene Knoten [mm]i,j[/mm] mit [mm]d(i),d(j)\ge 6[/mm].
>
> (d(i) sei der Grad des Knoten i)
>
> Daraus soll folgen, dass [mm]|E|\ge 2|V|+2[/mm],wobei
> [mm]|E|[/mm]= Anzahl
> der Kanten von G (mit Vielfachheit gezählt)
> [mm]|V|[/mm]= Anzahl der Knoten von G
>
> Ich weiß, dass [mm]|E|=\frac{1}{2}\sum_{i\in V}d(i)[/mm]. Aber
> weiter komm ich nicht. Muss wohl relativ trivial sein. Aber
> seh ich nicht, wie man auf die Abschätzung kommt.
>
> Könnte mir jemand bitte einen Hinweis geben?
> Danke!
>
> VG
> Fry
Hallo Fry,
ich fürchte, dass die Behauptung falsch ist.
Gegenbeispiel: Graph mit $\ V\ =\ [mm] \{1,2,3\}$ [/mm] und d(1)=d(2)=6 , d(3)=0
(6-fache Kante zwischen 1 und 2; dritter Punkt ohne Kante)
Nach meiner Ansicht erfüllt dieser Graph die Voraussetzungen,
aber nicht die Behauptung.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 04:01 Sa 02.06.2012 | | Autor: | Fry |
Hey Al,
danke, guter Einwand. Also hier steht," |V| is the number of vertices of G."...
Was wäre denn, wenn |V| nur die Anzahl der Knoten mit Grad>0 wäre?
Könnte man das dann ableiten?
LG
Fry
|
|
|
| |
|
> Hey Al,
>
> danke, guter Einwand. Also hier steht," |V| is the number
> of vertices of G."...
> Was wäre denn, wenn |V| nur die Anzahl der Knoten mit
> Grad>0 wäre?
> Könnte man das dann ableiten?
>
> LG
> Fry
Guten Morgen Fry,
gerade weil die Bedingung (1) so formuliert war:
(1) $ [mm] d(i)\ge [/mm] 4 $, falls $ d(i)>0 $ und $ [mm] i\in [/mm] V $
nahm ich an, dass es auch Knoten mit d(i)=0 geben darf.
Andernfalls sollte doch die Forderung d(i)>0 (oder gleich
[mm] d(i)\ge4 [/mm] ) für alle i als Voraussetzung gestellt werden.
LG Al
|
|
|
| |
|
> Hey Al,
>
> danke, guter Einwand. Also hier steht," |V| is the number
> of vertices of G."...
> Was wäre denn, wenn |V| nur die Anzahl der Knoten mit
> Grad>0 wäre?
> Könnte man das dann ableiten?
>
> LG
> Fry
Ich denke, dass du in diesem Fall ganz einfach die schon
genannte Formel
$ [mm] |E|=\frac{1}{2}\sum_{i\in V}d(i) [/mm] $
einsetzen kannst. Es haben ja dann alle Summanden d(i)
mindestens den Wert 4 , und zudem wissen wir, dass ent-
weder einer davon sogar mindestens 8 oder aber zwei davon
mindestens 6 betragen. Daraus ergibt sich dann so ziemlich
direkt die behauptete Ungleichung.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:20 Sa 02.06.2012 | | Autor: | Fry |
Vielen Dank,
jetzt hab ich nochmal eine andere Frage. Die beiden obige Eigenschaften
(1) [mm] $d(i)\ge [/mm] 4$, falls $d(i)>0$ und [mm] $i\in [/mm] V$
(2) Ferner existiere entweder ein [mm] $i\in [/mm] V$ mit [mm] $d(i)\ge [/mm] 8$
oder es existieren zwei verschiedene Knoten $i,j$ mit [mm] $d(i),d(j)\ge [/mm] 6$.
+(3) Vielfachheit der Kante e={i,j} [mm] $\ge [/mm] 2$,
wenn die Vielfachheit>0 ist.
sollen daraus folgen, dass für den Graph G gilt:
(1)* G ist Vereinigung von (einfachen) Kreisen
(Beim Kreis werden vom einen Startknoten Kanten "hintereinander gereiht" und die letzte Kante hat den Startknoten als Endknoten. Es tauchen natürlich keine Kanten mehrfach auf.)
(2)* G besitzt keine Knoten mit d(i)=1
(3)* Die Kantenmenge von G ist NICHT disjunkte Vereinigung der Kantenmengen von doppelten Kreisen (doppelter Kreis=Kreis, deren Kanten die Vielfachheit 2 haben)
Jetzt frag ich mich, welche der Eigenschaften (1)*-(3)* für welche Aussage (1)-(3) herangezogen werden.
Also ich denke, dass man aus (2)* die Eigenschaft (3) schließt.
Aber was benötigt man alles z.B. für die Aussage (2) ?
VG
Fry
|
|
|
| |
|
> Vielen Dank,
>
> jetzt hab ich nochmal eine andere Frage. Die beiden obige
> Eigenschaften
> (1) [mm]d(i)\ge 4[/mm], falls [mm]d(i)>0[/mm] und [mm]i\in V[/mm]
> (2) Ferner
> existiere entweder ein [mm]i\in V[/mm] mit [mm]d(i)\ge 8[/mm]
> oder es
> existieren zwei verschiedene Knoten [mm]i,j[/mm] mit [mm]d(i),d(j)\ge 6[/mm].
>
> +(3) Vielfachheit der Kante e={i,j} [mm]\ge 2[/mm],
> wenn die
> Vielfachheit>0 ist.
>
> sollen daraus folgen, dass für den Graph G gilt:
>
> (1)* G ist Vereinigung von (einfachen) Kreisen
> (Beim Kreis werden vom einen Startknoten Kanten
> "hintereinander gereiht" und die letzte Kante hat den
> Startknoten als Endknoten. Es tauchen natürlich keine
> Kanten mehrfach auf.)
> (2)* G besitzt keine Knoten mit d(i)=1
> (3)* Die Kantenmenge von G ist NICHT disjunkte Vereinigung
> der Kantenmengen von doppelten Kreisen (doppelter
> Kreis=Kreis, deren Kanten die Vielfachheit 2 haben)
>
>
> Jetzt frag ich mich, welche der Eigenschaften (1)*-(3)*
> für welche Aussage (1)-(3) herangezogen werden.
>
>
> Also ich denke, dass man aus (2)* die Eigenschaft (3)
> schließt.
> Aber was benötigt man alles z.B. für die Aussage (2) ?
>
> VG
> Fry
>
Hallo,
das wird ja allmählich etwas kompliziert. Weiß nicht, ob ich
da dabei bleiben werde ...
Vorweg ein paar Fragen:
1.) die Graphen sind doch ungerichtet, oder ?
2.) was genau versteht man unter der Vereinigung von [mm] (V_1,E_1)
[/mm]
und [mm] (V_2,E_2) [/mm] ?
Von [mm] V_1 [/mm] und [mm] V_2 [/mm] nimmt man sicher die "normale" Vereini-
gungsmenge - aber was ist z.B. in folgendem Fall:
Die (beiden Graphen gemeinsamen) Knoten P und Q seien im
ersten Graph durch 2 Kanten verbunden, im anderen durch 3
Kanten. Durch wieviele Kanten sind sie dann im vereinigten
Graphen verbunden ? (3 oder 5 oder ev. auch 4 ??)
Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:55 Sa 02.06.2012 | | Autor: | Fry |
Also die Graphen sind ungerichtet...
Ah, sehe das Problem.
Also in deinem Beispiel hätte die Kante die Vielfachheit 5.
Mmmm...definitionsmäßig würde das wohl nicht der Vereinigung von [mm] E_1 [/mm] und [mm] E_2
[/mm]
entsprechen, oder?
Fry
|
|
|
| |
|
>
> Also die Graphen sind ungerichtet...
>
> Ah, sehe das Problem.
> Also in deinem Beispiel hätte die Kante die Vielfachheit
> 5.
> Mmmm...definitionsmäßig würde das wohl nicht der
> Vereinigung von [mm]E_1[/mm] und [mm]E_2[/mm]
> entsprechen, oder?
Nun , eben Definitionssache.
Gemeint ist also offenbar, dass man die Kantenmengen
der beiden Graphen als disjunkte Mengen betrachten
soll. Es hätte mich nur interessiert, wie denn der Begriff
der Vereinigung von Graphen bei euch (Skript ?)
genau definiert wurde - wenn überhaupt (???).
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:40 Sa 02.06.2012 | | Autor: | Fry |
Leider überhaupt nicht, da das ganze aus nem Paper stammt und der Autor es leider nicht für notwendig hielt, genau zu erklären, wie er das meint...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 So 17.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
