def.: kreuzung im graph? |
| 01.08.2013, 11:50 | Hm... | Auf diesen Beitrag antworten » |
| def.: kreuzung im graph? ich finde die definition einer kreuzung in einem graphen G=(V,E) nicht - im internet stehen nur algorithmen wie man die anzahl an kreuzungen herausfinden kann. könnt ihr mir sagen wie eine kreuzung im graph definiert ist? meine def. war bisher: (i,j) kreuzt (i',j'), wenn: i<i'<j<j' aber irgendwie fehlt da noch eine weitere möglichkeit schätze ich, denn sowas soll auch eine kreuzung sein: i<i'<j'<j ich brauche die definition um den beweis für das theorem hier zu verstehen: "zu jedem matching gibt es ein matching ohne kreuzungen mit der gleichen anzahl an seiten" beweis per: lemma: "jede unkreuzung in matching M, reduziert die anzahl an kreuzungen in M" |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
Verschoben!