Einfacher Pfad mit Länge d |
29.11.2011, 08:47 | Nadine1987CB | Auf diesen Beitrag antworten » |
Einfacher Pfad mit Länge d Sei (V,E) ein Graph mit Minimalgrad ? d zeigen Sie, dass es einen einfachen Pfad der Länge d gibt. Dabei ist ein einfacher Pfad ein Folge von Knoten {v1,...,vk}, so dass vi,vi+1 element von E und {vi,vi+1}{vj,vj+1} für ij. Meine Ideen: Also ich hab schon ein wenig mit Beispielen rumprobiert. ICh verstehe auch die Definition bzw was ein einfacher Pfad ist. Die Länge eines Pfades ist ja d=n-1. Nur komme ich mit diesem minimalgrad nicht zurande. Folgendes Bsp: .-.-. (Graph: Punkte sind Knoten, Striche die Kanten) Der Minimalgrad ist ja 1. Nur die Länge des Pfades ist ja 2. Somit kann der Minimalgrad wie in diesem Bsp nicht grösser gleich der Länge d sein. Der Minimalgrad ist doch der kleinste Grad eines Knotens in einen Graphen. |
||
29.11.2011, 08:54 | Nadine1987CB | Auf diesen Beitrag antworten » |
Graph mit Minamalgrad grösser gleich d. In meinem ersten Post steht da ein Fragezeichen. Hoffe ich habe im richtigen Forum gepostet, habe auf dies chnelle keines für Graphentheorie gefunden. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|