Potřebuji sestrojit graf d-regular expanderu pro některé malé pevné d (jako 3 nebo 4) n vrcholů.
Co je nejjednodušší způsob, jak toho dosáhnout v praxi? Sestavení náhodného d-regulárního grafu, který se ukázal jako a.a.s. expandér?
Četl jsem také o konstrukcích Margulis a grafech Ramanujan, které jsou expandéry a konstrukcí využívající produkt cik-cak. Wikipedia poskytuje pěkný, ale velmi krátký přehled: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Jakou metodu však v praxi zvolím?
Zdá se mi, že se tyto metody implementují velmi komplikovaně, zejména proto, že jsou pochopitelné, a možná docela konkrétní. Neexistují jednodušší metody, které by mohly být založeny na permutacích nebo tak, aby bylo možné prakticky vygenerovat sekvenci d-regulárních expandérových grafů?
Je možná jednodušší sestrojit d-regulární bipartitní expandérové grafy?
Mám také další otázku: A co rodiny špatných expandérů d-regulárních? Má takový pojem smysl? Lze sestavit rodinu grafů d-regulárních (které jsou samozřejmě spojeny), která je v co možná nejhorší smysl pro expandér?
Předem děkujeme.
Komentáře
- Existují jednodušší explicitní konstrukce než ty, které jste uvedli , ale náhodné grafy by měly stačit a mít lepší parametry.
- Můžete uvést názvy nebo odkazy na stavby? Lepšími parametry myslíte lepší (okrajovou) expanzi, myslím?
- Andr á s uvedl příklad, který jsem měl na mysli, ale obecně jsou náhodné grafy (téměř vždy) lepší než explicitní konstrukce. Nejen, že je rozšíření hrany větší, an Další podobná vlastnost, která je užitečná pro váš algoritmus, je pravděpodobně automaticky uspokojena náhodnými grafy.
- Dobře, pro stupeň 3, Andr á s příklad nebo náhodné grafy se mi jeví jako dost dobré pro moji žádost. Bylo by zajímavé, zejména s ohledem na náhodné grafy, sestrojit rodinu grafů 3-reg, která není expandérem. Ale to je pravděpodobně velmi těžké nebo nemožné?
- Vezměte sjednocení $ K_4 $ s. Pokud chcete propojený graf, odstraňte z každého $ K_4 $ jednu hranu (tvořící graf známý jako diamantový graf) a spojte je v cyklu.
Odpovědět
Pokud vám nevadí grafy se samoobslužnými smyčkami, je nejjednodušší rodina expandérů pravděpodobně tato, což dává expandérům 3 řádky.
Začněte s nějakým prvočíslem $ p $ a vytvořte vrcholy očíslované od $ 0 $ do $ p-1 $. Pro každý vrchol $ u \ ne 0 $ připojte $ u $ k $ u-1 $ a $ u + 1 $ , modulo $ p $. Také připojte $ u $ k jedinečnému vrcholu $ v $ tak, aby $ uv \ equiv 1 \ mod p $.
Jako příklad lze uvést 7-vertexový graf v rodině 7-cyklus s vrcholy číslovanými postupně kolem cyklu; na $ 6 $, $ 0 $ a $ 1 $ jsou vlastní smyčky; konečně existují akordy spojující $ 3 $ a $ 5 $ a $ 2 $ a $ 4 $.
Další diskuse a odkazy viz https://mathoverflow.net/questions/124708/an-expander-graph . Při hledání je spousta podrobnějších ukazatelů. “ expander „at CSTh eory , Math.SE a MO .
Jak zdůrazňuje Yuval Filmus, náhodná konstrukce pravděpodobně obecně poskytne lepší výsledky, ale samozřejmě nemusí přinést expandér (zejména u malých grafů).
Komentáře
- Děkujeme za poznámku. Už jsem dříve hledal expandéry na jiných webech, ale ne na MO, zdá se, že existuje opravdu více výsledků.
Odpověď
Vzhledem k náhodnému pravidelnému grafu je expandér whp (postupujte podle odkazu uvedeného v dokumentaci níže uvedeného kódu MATLAB), jednou jsem použil následující: