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

z Wikipédie, slobodnej encyklopédie
Jump to navigation Jump to search

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.