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

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 

Kategória:Teória grafov