n 개의 정점의 작은 고정 d (예 : 3 또는 4)에 대해 d-regular expander graph를 구성해야합니다.
실제로 이것을 수행하는 가장 쉬운 방법은 무엇입니까? 임의의 d- 정규 그래프를 구성하는 것은 확장기로 입증 되었습니까?
또한 확장기 및 지그재그 제품을 사용한 구성 인 Margulis 구성 및 Ramanujan 그래프에 대해서도 읽었습니다. Wikipedia는 훌륭하지만 매우 짧은 개요를 제공합니다. http://en.wikipedia.org/wiki/Expander_graph#cite_note-10
그러나 실제로 어떤 방법을 선택합니까?
나를 위해, 이러한 방법은 구현하기가 매우 복잡하고 특히 이해하기가 매우 복잡해 보입니다. d- 정규 확장기 그래프의 시퀀스를 실제로 생성하기위한 순열 등에 기반한 더 쉬운 방법이 없습니까?
d- 정규 이분 확장기 그래프를 구성하는 것이 더 쉬울까요?
나는 또 다른 질문이 있습니다 : 나쁜 d-regular 확장기의 가족은 어떻습니까? 그러한 개념이 의미가 있습니까? 확장기의 의미에서 가능한 한 나쁜 d- 정규 그래프 (물론 연결된) 패밀리를 구성 할 수 있습니까?
미리 감사드립니다.
답변
자체 루프가있는 그래프가 마음에 들지 않으면 “가장 쉬운”확장기 제품군이 아마도 가장 일반적인 확장 기일 것입니다.
소수 소수 시작하여 0 에서 p – 1 사이의 정점을 구성하십시오 . 모든 정점 u ≠ 0 에 대해 u 를 u − 1에 연결 하고 u + 1 , 모듈로
p0
p−1
u≠0
u
u−1
u+1
합니다. 또한 연결 U를 고유 정점에 V 되도록 유 v에 ≡ 1
pu
v
.
uv≡1modp예를 들어, 패밀리의 7- 정점 그래프는 정점 주위에 정점이 번호가 매겨진 7-주기입니다. , 0 및 1 에 자체 루프가 있습니다 . 마지막으로, 화음이 합류합니다
60
1
3
5
2
4
자세한 논의 및 참조는 /mathpro/124708/an-expander-graph 를 참조 하십시오 . CSTheory , Math.SE 및 MO 에서 “확장자”를 검색하면 더 자세한 포인터가 많이 있습니다 .
Yuval Filmus가 지적한 바와 같이, 임의의 구성은 일반적으로 더 나은 결과를 제공 할 가능성이 있지만 물론 확장기 (특히 작은 그래프의 경우)를 산출하지 못할 수 있습니다.
답변
임의의 정규 그래프가 확장기 whp라고 가정하면 (아래 링크 된 MATLAB 코드의 문서에 제공된 참조를 따르십시오), 나는 다음을 사용했습니다.