|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Gujgiczer Anna: Gráfkódok |
|
|||
|
|
||||
|
||||
| Két, azonos csúcshalmazon definiált, $G_1$ és $G_2$ gráf szimmetrikus differenciája az a gráf, melynek csúcshalmaza megegyezik a $G_1$ és $G_2$ gráfok csúcshalmazával, és amelynek éleit azok a csúcspárok alkotják, melyek a $G_1$ és $G_2$ gráfok pontosan egyikében szomszédosak. Érdekes megvizsgálni, hogy egy $n$ méretű közös csúcshalmazon legfeljebb mennyi gráf adható úgy, hogy közülük bármely kettő szimmetrikus differenciája kielégítsen valamilyen előírt feltételt. Ha például azt a feltételt választjuk, hogy ez a differencia legalább $d$ élet tartalmazzon, akkor visszakapjuk a klasszikus kódelméleti kérdést: Legfeljebb mennyi $m$ hosszú bináris kód adható úgy, hogy közülük bármely kettő legalább $d$ helyen különbözzön? Meggondolható, hogy $m = \binom{n}{2}$ választással ez tényleg ugyanaz a probléma, ha a bináris kódokra úgy tekintünk, mint az $n$ csúcsú gráfok élhalmazait leíró karakterisztikus vektorokra. Azonban vizsgálhatunk általánosabb tulajdonságokat is, mint például az összefüggőséget vagy azt, hogy an-e Hamilton-út a gráfban vagy akár egy-egy rögzített részgráf tartalmazását is. Ebben az előadásban néhány eredményt szeretnék ismertetni egy erről a problémakörről szóló cikkünkből, melynek társszerzői Alon, Körner, Milojević és Simonyi. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013