Křížení čísel grafů - Crossing Numbers of Graphs

Křížení čísel grafů je kniha z matematiky na minimální počet přechodů hran potřeba v grafové výkresy. Napsal to Marcus Schaefer, profesor výpočetní techniky na Univerzita DePaul, a publikováno v roce 2018 CRC Press ve své knižní sérii Diskrétní matematika a její aplikace.

Témata

Hlavní text knihy má dvě části, tradičně definované číslo křížení a variace čísla křížení, za kterými následují dvě přílohy^[1] poskytnutí podkladového materiálu pro teorie topologických grafů a teorie výpočetní složitosti.^[2]

Po seznámení s problémem se první kapitola zabývá čísly křížení kompletní grafy (počítaje v to Hillův domnělý vzorec pro tato čísla) a kompletní bipartitní grafy (Turánova továrna na cihly a dohad o čísle křížení Zarankiewicze), což opět dává domnělý vzorec).^[2][3] Zahrnuje také nerovnost křížení čísel a Věta Hanani – Tutte na paritě přechodů.^[1] Druhá kapitola se týká dalších speciálních tříd grafů včetně grafové produkty (zejména výrobky z cyklické grafy ) a hyperkrychlové grafy.^[2][3] Po třetí kapitole týkající se čísla křížení s parametry grafu včetně šikmost, šířka půlení, tloušťka, a (prostřednictvím Albertsonova domněnka ) chromatické číslo, poslední kapitola části I se týká výpočetní složitost hledání kreseb grafů minimálního křížení, včetně výsledků, že problém je obojí NP-kompletní a fixovatelný parametr.^[1][2][3]

Ve druhé části knihy se dvě kapitoly týkají přímočarého čísla křížení, které popisuje grafové výkresy, ve kterých musí být hrany reprezentovány spíše jako přímkové segmenty než jako libovolné křivky, a Fáryho věta že každý rovinný graf lze kreslit bez křížení tímto způsobem. Další kapitola se týká 1-rovinné grafy a přidružené místní číslo přechodu, nejmenší číslo k tak, že graf lze nakreslit maximálně k přechody na hranu. Týká se to dvou kapitol vkládání knih a řetězcové grafy, a další dvě kapitoly se týkají variací čísla křížení, které počítají křížení různými způsoby, například počtem párů hran, které se protínají nebo které překračují lichý počet opakování. Závěrečná kapitola části II se týká závity a problém najít výkresy s maximálním počtem křížení.^[2][3]

Publikum a příjem

Knihu lze použít jako pokročilou učebnici a pro toto použití obsahuje cvičení.^[2][3] Předpokládá však, že její čtenáři již obě znají teorie grafů a návrh a analýza algoritmy.^[2] Recenze knihy, L. W. Beineke nazývá jej „cenným příspěvkem“ pro prezentaci mnoha výsledků v této oblasti.

Reference