2021. 09. 23. 12:30 - 2021. 09. 23. 13:30
Bolyai Intézet, Szeged, Bolyai épület, Aradi vértanúk tere, 6720 Magyarország
-
-
-
-
Esemény típusa:
szeminárium
Szervezés:
Külsős
-
Szegedi Szemináriumok
Leírás
SZTE, TTIK, Bolyai Intézet, Kerékjártó szeminárium
Absztrakt. Legyen $\Gamma=(V,E)$ egy véges, egyszerű, irányítatlan gráf. Jelölje $d(u,v)$ az $u$ és $v$ csúcsok távolságát, $N[s]$ pedig az $s$ csúcstól legfeljebb $1$ távolságra lévő csúcsok halmazát.
- Csúcsok egy $S=\{v_1,\ldots,v_n\}\subset V$ részhalmaza elkülöníti a $v$ csúcsot, ha a távolságokból képzett $(d(v,v_1),d(v,v_2),\ldots,d(v,v_n))$ sorozat egyértelműen meghatározza $v$-t. Az $S$ megoldóhalmaza $\Gamma$-nak, ha $V$ minden elemét elkülöníti.
- Csúcsok egy $D$ részhalmaza domináló halmaz ha $V\subset \bigcup_{d\in D}N[d]$.
- Az $s$ csúcs elválasztja az $u$ és $v$ csúcsokat, ha $u$ és $v$ közül pontosan az egyik $N[s]$-beli. Csúcsok egy $S\subset V$ halmaza szeparáló halmaz, ha $S$ a $\Gamma $ bármely két csúcsát elválasztja.
- Csúcsok egy $C\subset V$ halmaza azonosító kód, ha egyszerre domináló és szeparáló halmaz.
Az előadásban olyan gráfok megoldóhalmazairól és azonosító kódjairól lesz szó, melyek különböző véges geometriai struktúrákból származnak (pl. projektív és affin síkok és terek, általánosított négyszögek Levi gráfjai). Egyrészt általános becsléseket adunk ezen halmazok méretére, másrészt jónéhány (gyakran optimális) konstrukciót mutatunk.