Rainbow Subgraph in gültigem Kanten-gefärbtem Graph |
| 20.10.2017, 15:10 | MatheMarco | Auf diesen Beitrag antworten » |
| Rainbow Subgraph in gültigem Kanten-gefärbtem Graph Im Kurs randomisierte Algorithmen und probabilistische Methodik wurde uns die folgende Frage gestellt: Es geht zu zeigen: Auf einem gültigem-Kanten gefärbtem Graph mit n Knoten, existiert ein Subgraph mit n^(1/4) Knoten, der ein Rainbow (Alle Kanten haben paarweise verschiedene Farben) ist. Wobei n genügend gross ist. Meine Ideen: Wir haben uns verschiedene Ansätze überlegt: 1. einen zufällig gefärbten Graph zu nehmen und die Wahrscheinlichkeit, dass dieser einen Rainbow besitzt auszurechnen. Wir scheiten allerdings an der zufälligen gültigen Färbung. 2. einen zufälligen Subgraph zu nehmen und die Wahrscheinlichkeit dass dieser ein Rainbow ist zu betrachten. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
