n 꼭지점의 작은 고정 d (예 : 3 또는 4)에 대해 d- 정규 확장 그래프를 구성해야합니다.
무엇을 실제로 이것을 수행하는 가장 쉬운 방법은 무엇입니까? a.a.s로 입증 된 임의의 d- 정규 그래프 생성 확장기?
또한 확장기 인 Margulis 구조와 Ramanujan 그래프와 지그재그 제품을 사용한 구조에 대해서도 읽었습니다. Wikipedia는 훌륭하지만 매우 짧은 개요를 제공합니다. http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 하지만 실제로 어떤 방법을 선택해야합니까?
저에게 이러한 방법은 모두 구현하기가 매우 복잡하고 특히 이해하기가 매우 복잡해 보일 수 있습니다. d- 정규 확장기 그래프의 시퀀스를 실제로 생성하기 위해 순열 등을 기반으로하는 더 쉬운 방법이 없습니까?
d- 정규 이분 확장기 그래프를 구성하는 것이 더 쉬울까요?
또 다른 질문이 있습니다. 불량 d- 정규 확장기의 패밀리는 어떻습니까? 그런 개념이 타당합니까? 가능한 한 나쁜 d- 정규 그래프 패밀리 (물론 연결됨)를 구성 할 수 있습니까? 확장기의 느낌?
미리 감사합니다.
댓글
- 나열한 것보다 더 쉬운 명시 적 구성이 있습니다. ,하지만 무작위 그래프는 더 나은 매개 변수를 가져야합니다.
- 구성의 이름이나 참조를 제공 할 수 있나요? 매개 변수가 더 우수하면 더 나은 (가장자리) 확장을 의미하는 것 같습니다.
- Andr á는 제가 염두에 둔 예를 제공했지만 일반적으로 임의 그래프가 명시 적 구성보다 (거의 항상) 더 좋습니다. 가장자리 확장이 더 클뿐만 아니라 an 알고리즘에 도움이되는 다른 유사한 속성은 아마도 임의의 그래프에 의해 자동으로 충족 될 것입니다.
- 좋아, 3 차의 경우 Andr á의 예 또는 임의의 그래프 내 응용 프로그램에 충분할 것 같습니다. 확장기가 아닌 3-reg 그래프 패밀리를 구성하는 것은 특히 랜덤 그래프와 관련하여 흥미로울 것입니다. 그러나 이것은 아마도 매우 어렵거나 불가능할까요?
- $ K_4 $ s의 합집합을 가져옵니다. 연결된 그래프를 원하면 $ K_4 $ (다이아몬드 그래프로 알려진 그래프를 형성)에서 하나의 가장자리를 제거하고 주기적으로 연결합니다.
Answer
자체 루프가있는 그래프가 마음에 들지 않는다면 “가장 쉬운”확장기 제품군은 아마도이 확장기 제품군이 3 정규 확장기를 제공합니다.
소수 $ p $로 시작하여 $ 0 $에서 $ p-1 $까지 번호가 매겨진 정점을 구성합니다. 모든 정점 $ u \ ne 0 $에 대해 $ u $를 $ u-1 $ 및 $ u + 1 $에 연결합니다. , 모듈로 $ p $. $ uv \ equiv 1 \ mod p $가되도록 $ u $를 고유 한 정점 $ v $에 연결합니다.
예를 들어 패밀리의 7-vertex 그래프는 다음과 같습니다. 주기를 따라 순차적으로 번호가 매겨진 정점이있는 7주기. $ 6 $, $ 0 $, $ 1 $에는 자체 루프가 있습니다. 마지막으로 $ 3 $와 $ 5 $, $ 2 $와 $ 4 $를 연결하는 코드가 있습니다.
자세한 논의와 참고 자료는 https://mathoverflow.net/questions/124708/an-expander-graph 를 참조하세요. ” 확장기 “의 CSTh eory , Math.SE 및 월 .
Yuval Filmus가 지적했듯이 무작위 구성은 일반적으로 더 나은 결과를 제공 할 가능성이 높지만 물론 확장기를 생성하지 못할 수도 있습니다 (특히 작은 그래프의 경우).
댓글
- 발언 해 주셔서 감사합니다. 이전에 다른 사이트에서 확장기를 검색했지만 MO에서는 검색하지 않았습니다. 실제로 더 많은 결과가있는 것 같습니다.
답변
무작위 일반 그래프가 확장기 인 경우 whp (아래 링크 된 MATLAB 코드 문서에 제공된 참조를 따르십시오), 저는 한 번 다음을 사용했습니다.