태그 보관물: expanders

expanders

실제 확장 그래프를 실제로 구성하는 방법은 무엇입니까? 제공합니다. http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 그러나 실제로 어떤 방법을

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 에 대해 uu 1에 연결 하고 u + 1 , 모듈로

p

0

p−1

u≠0

u

u−1

u+1

합니다. 또한 연결 U를 고유 정점에 V 되도록v에 1

p

u

v

.

uv≡1modp

예를 들어, 패밀리의 7- 정점 그래프는 정점 주위에 정점이 번호가 매겨진 7-주기입니다. , 01 에 자체 루프가 있습니다 . 마지막으로, 화음이 합류합니다

6

0

1

3

5

2

4

자세한 논의 및 참조는 /mathpro/124708/an-expander-graph 를 참조 하십시오 . CSTheory , Math.SEMO 에서 “확장자”를 검색하면 더 자세한 포인터가 많이 있습니다 .

Yuval Filmus가 지적한 바와 같이, 임의의 구성은 일반적으로 더 나은 결과를 제공 할 가능성이 있지만 물론 확장기 (특히 작은 그래프의 경우)를 산출하지 못할 수 있습니다.


답변

임의의 정규 그래프가 확장기 whp라고 가정하면 (아래 링크 된 MATLAB 코드의 문서에 제공된 참조를 따르십시오), 나는 다음을 사용했습니다.

http://www.mathworks.com/matlabcentral/fileexchange/29786-random-regular-generator/content/randRegGraph/createRandRegGraph.m


답변