Rectilinear Crossing Number
Napísané: Pi Mar 06, 2009 2:21 am
Rectilinear Crossing Number je matematický projekt, ktorý sa snaží vyriešiť rôzne výpočtové a kombinačné problémy vychádzajúce z konečného počtu bodov v Euklidovej rovine.
Sem patrí niekoľko problémov z teórie grafov, kde spojnice medzi akýmikoľvek dvoma bodmi sú priame (grafom je v tomto prípade abstraktné znázornenie skupiny objektov, kde niektoré objekty sú navzájom spojené).
Základná otázka znie: aký je najmenší počet priesečníkov v grafe, ktorý vznikol vzájomným prepojením všetkých n bodov v rovine priamymi spojnicami? Uvažujeme všeobecné rozloženie bodov v rovine, kde tri rôzne body neležia na jednej priamke.
Sem patrí niekoľko problémov z teórie grafov, kde spojnice medzi akýmikoľvek dvoma bodmi sú priame (grafom je v tomto prípade abstraktné znázornenie skupiny objektov, kde niektoré objekty sú navzájom spojené).
Základná otázka znie: aký je najmenší počet priesečníkov v grafe, ktorý vznikol vzájomným prepojením všetkých n bodov v rovine priamymi spojnicami? Uvažujeme všeobecné rozloženie bodov v rovine, kde tri rôzne body neležia na jednej priamke.