Ročníkový projekt

Názov projektu: Experimentálne potvrdenie/vyvrátenie Ehrenborgovej domnienky

Meno študenta: Martin Košovský

Email: kosovsky2@uniba.sk

Školiteľ: RNDr. Peter Kostolányi, PhD.

Email školiteľa: kostolanyi@fmfi.uniba.sk

Stručný popis: Ehrenborgova domnienka (Ehrenborg conjecture) je domnienka, ktorá tvrdí, že pre akýkoľvek bipartitný graf G s m vrcholmi na jednej strane a n vrcholmi na druhej strane, počet kostier grafu G nepresahuje súčin stupňov vrcholov delený súčinom veľkostí oboch strán.

Ciele:

• Oboznámiť sa s problémom, prečítať vybranú súvisiacu literatúru.
• Vybrať vhodný programovací jazyk, ktorý bude dostatočne rýchly, aby sme mohli testoval domnienku na čo najväčšej množine bipartitných grafov v rozumnom čase.
• Navrhnúť a naprogramovať program, ktorý bude generovať bipartitné grafy, počítať ich kostry a testovať túto domnienku.

Zimný semester:

• report
• zdrojové kody

Letný semester:

• report
• zdrojové kody