Priesečníkové číslo (teória grafov)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Priesečníkové číslo je v teórii grafov najmenší možný počet priesečníkov hrán daného grafu pri ľubovoľnom jeho rovinnom nakreslení. Graf sa nazýva rovinný práve vtedy, keď je jeho priesečníkové číslo rovné nule.

Problém určenia priesečníkového čísla grafu sa po prvýkrát objavil v súvislosti s tzv. Turánovým problémom tehelne, v ktorom sa matematik Pál Turán pýtal na priesečníkové číslo úplného bipartitného grafu Km,n.

Zdroj[upraviť | upraviť zdroj]

Tento článok je čiastočný alebo úplný preklad článku Crossing number (graph theory) na anglickej Wikipédii.