Rectilinear Crossing Number

Diskusia k ostatným projekom a k projektom vo vývojovom resp. prípravnom štádiu

Moderátor: Moderátori

Používateľov profilový obrázok
Hefto99
Príspevky: 769
Dátum registrácie: Po Feb 05, 2007 11:59 pm
Bydlisko: Zürich, Schweiz

Rectilinear Crossing Number

Príspevok od používateľa Hefto99 »

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.
Obrázok
Napísať odpoveď