โครงสร้างสำหรับกราฟสุ่มพร้อมโครงสร้าง
ความเป็นมา
[คุณสามารถข้ามสิ่งนี้และไปที่คำจำกัดความได้ทันที]
คุณสมบัติที่สำคัญของกราฟหรือเครือข่าย (สุ่ม) คือ:
การกระจายองศา $p(d)$ (เอกซ์โพเนนเชียลปัวซองหรือกฎหมายกำลัง)
ระดับค่าเฉลี่ย $\bar{d}$
ค่าสัมประสิทธิ์การจัดกลุ่มเฉลี่ย $\bar{C}$
ระยะทางเฉลี่ย $L$ และเส้นผ่านศูนย์กลาง $D$
กราฟที่สร้างแบบสุ่มมักจะต้องใช้เพื่อแสดงคุณสมบัติของโลกขนาดเล็กนั่นคือ$L\propto \log N$ และ $\bar{C}$ก็“ ไม่เล็ก” มีแบบจำลองกราฟแบบสุ่มหลายแบบที่ระบุเงื่อนไขเหล่านี้อย่างน้อยหนึ่งข้อ:
- รุ่นWatts-Strogatz (พร้อมโครงตาข่ายวงแหวนปกติ)
- รุ่นBarabasi-Albert (พร้อมไฟล์แนบที่ต้องการ)
- รูปแบบการกำหนดค่า (วนเวียนอยู่กับการศึกษาระดับปริญญาให้รับผิดชอบ. กระจาย)
- รุ่นนิวแมน (ผสมผสานโครงสร้างชุมชน )
ในขณะที่โมเดล Watts-Strogatz และ Barabasi-Albert เป็นการปรับเปลี่ยนโมเดลErdős – Rényiและแบบจำลอง Newman เป็นลักษณะทั่วไปเฉพาะของโมเดลการกำหนดค่า แต่ฉันสงสัยว่ามี "meta-model" อยู่แล้วที่พยายามรวม ดีที่สุดในบรรดารุ่นเหล่านี้ (คำขออ้างอิง)
โดยสรุปทั้งแบบจำลองของ Watts-Strogatz และ Newman ฉันต้องการตรวจสอบกราฟแบบสุ่มที่"สอดแทรกระหว่างโครงสร้างแบบสุ่มที่ใกล้เคียงกับกราฟ ER และ[กราฟทั่วไปบางส่วน] " (อ้างอิงจากWikipedia )
สำหรับสิ่งนี้ฉันต้องการมีกราฟปกติจำนวนมากที่สามารถทำได้
เป็นสัญลักษณ์และแจกแจงอย่างเป็นระบบ
สร้างขึ้นได้ง่ายจากสัญลักษณ์ของพวกเขา (เช่นเมทริกซ์ adjacency) และ
อาจมีนิพจน์รูปแบบปิดสำหรับลักษณะของโลกใบเล็ก $L$ และ $\bar{C}$
กราฟปกติใดที่ฉันมีอยู่ในใจสามารถอธิบายได้ง่ายที่สุดด้วยตัวอย่าง
คำจำกัดความ
ให้การกำหนดค่าจุดยอดเป็นกราฟที่แสดงถึงจุดยอด $\nu$ กับเพื่อนบ้านหลายคน $\nu_0,\nu_2,\dots,\nu_{d-1}$ และเส้นทางที่สั้นที่สุด (ตามความยาวโดยพลการ) ระหว่างเพื่อนบ้านที่ติดต่อกันแต่ละคู่ $\nu_i, \nu_{i+1}$. การกำหนดค่าจุดยอดสามารถเข้ารหัสโดยสัญลักษณ์$(n_1.n_2.\dots.n_k)^m$ ซึ่งบอกว่า $\nu$ มีปริญญา $d = m \cdot k$ และล้อมรอบด้วย $m$- ลำดับระยะของ $n_i$-faces resp. รอบที่สั้นที่สุด (นี่ไม่ใช่อะไรนอกจากคำจำกัดความมาตรฐานของการกำหนดค่าจุดยอดในรูปทรงเรขาคณิตในภาษาของทฤษฎีกราฟ)
ตัวอย่าง:
กล่าวกันว่าจุดยอดมีการกำหนดค่าจุดยอดที่กำหนด $\Gamma$ เมื่อพื้นที่ใกล้เคียงพร้อมกับเส้นทางที่สั้นที่สุดระหว่างเพื่อนบ้านคือ isomorphic ถึง $\Gamma$. กราฟมีการกำหนดค่าจุดยอดที่กำหนด$\Gamma$ เมื่อจุดยอดทั้งหมดมีการกำหนดค่าจุดยอด $\Gamma$. การกำหนดค่าจุดยอดถูกกล่าวว่าสามารถรับรู้ได้เมื่อมีกราฟที่มี
ตอนนี้ให้พิจารณากราฟ จำกัด ซึ่งจุดยอดทั้งหมดมีการกำหนดค่าจุดยอดเหมือนกัน
คำถาม
เป็นการกำหนดค่าจุดยอดทั้งหมด $\Gamma$สามารถรับรู้ได้ด้วยกราฟที่มีขนาดตามอำเภอใจมากหรือน้อย? จะพิสูจน์หรือหักล้างสิ่งนี้ได้อย่างไร?
สิ่งนี้เกี่ยวข้องกับคำถามหากการกำหนดค่าจุดยอดทั้งหมด (ในความหมายของรูปทรงเรขาคณิต) ซึ่งไม่ได้กำหนดการเรียงต่อกันเป็นระยะของทรงกลม (เช่นรูปทรงหลายเหลี่ยมปกติ) กำหนดการเรียงต่อกันเป็นระยะของระนาบแบบยุคลิดหรือไฮเพอร์โบลิกหากมีการกำหนดค่าจุดยอดที่ไม่สามารถรับรู้ได้: ฉันจะตรวจสอบได้อย่างไรว่าการกำหนดค่าจุดยอดที่กำหนดนั้นสามารถรับรู้ได้หรือไม่?
สร้างกราฟที่มีการกำหนดค่าจุดยอดที่กำหนด $\Gamma$ ต้องเป็นจุดยอด - สกรรมกริยา?
เนื่องจากจำนวนจุดยอด (เท่ากัน) ของกราฟเชิงทรานซิทีฟสองจุดที่มีการกำหนดค่าจุดยอดเดียวกันจึงไม่รับประกันว่าเป็นไอโซมอร์ฟิก: โดยวิธีการทั่วไปสามารถกำหนด "รูปร่าง" ของพวกเขาได้ดังนั้นกราฟที่กำหนดเท่ากันสองกราฟจึงต้องเป็นไอโซมอร์ฟิก (ตัวอย่าง: ดูด้านล่าง)
มีวิธีที่เป็นระบบในการสร้างเมทริกซ์ adjacency สำหรับการกำหนดค่าจุดยอดและ "รูปร่าง" ที่กำหนดได้หรือไม่?
กับ "รูปร่าง" ผมหมายถึงสิ่งที่ Dolbilin และ Schulte เรียกว่า "คอมเพล็กซ์ย่าน (Coronas)" ในกระดาษของพวกเขาทฤษฎีบทท้องถิ่นสำหรับ monotypic tilings
ตัวอย่าง
พิจารณาการกำหนดค่าจุดยอด $(4)^4$ และ "รูปร่าง" ที่กำหนดโดยตัวเลข $(4, 6)$
เมื่อเชื่อมจุดยอดที่ด้านตรงข้ามของรูปร่างจุดยอดทั้งหมดมีการกำหนดค่าจุดยอดเหมือนกัน $(4)^4$ยิ่งกว่านั้นกราฟผลลัพธ์เป็นจุดยอด - สกรรมกริยา:
เราหาเส้นผ่านศูนย์กลาง $D = 5$สัมประสิทธิ์การจัดกลุ่ม $\bar{C} = 0$และระยะทางเฉลี่ย $L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$ เพื่อค้นหานิพจน์ที่ชัดเจนแบบปิดหรือเรียกซ้ำ (ขึ้นอยู่กับ $(n,m)$) ดูเหมือนจะเป็นไปได้
สำหรับ "รูปร่าง"
ด้วยการกำหนดค่าจุดยอดและจำนวนจุดยอดเดียวกันที่เราพบ $D = 5$ และระยะทางเฉลี่ย $L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$
สำหรับ "รูปร่าง"
ด้วยจำนวนจุดยอดใกล้เคียงกับที่เราพบ $D = 4$ และระยะทางเฉลี่ย $L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$.
หากคุณต้องการค่าสัมประสิทธิ์คลัสเตอร์ $\bar{C} = 1/2$ คุณสามารถเริ่มต้นด้วยการกำหนดค่าจุดยอด $(3.n)^m$, เช่น $(3.4)^2$:
น่าเสียดายที่การกำหนดค่านี้ไม่มีคุณสมบัติเนื่องจากไม่ได้เรียงระนาบ แต่เป็นทรงกลม (ก่อให้เกิดทรงลูกบาศก์ ) ดังนั้นคุณต้องเลือก$(3.4)^3$อย่างน้อย. ในการวาด "รูปร่าง" ที่สวยงามบางขนาดที่สามารถทำเป็นกราฟ จำกัด ด้วยการกำหนดค่าจุดยอด$(3.4)^m$, $m > 2$ต้องใช้รูปทรงเรขาคณิตที่เกินความจริง ในการหาเมทริกซ์ adjacency นั้นยากยิ่งกว่าอย่างที่ฉันเดา (ดูคำถาม 5) เส้นผ่านศูนย์กลางด้วย$D$ และระยะทางเฉลี่ย $L$ (เป็นนิพจน์ปิด)
หรือคุณสามารถเพิ่มขอบเป็นครึ่งหนึ่งของไฟล์ $n\cdot m$ $4$- รอบ (สุ่มเลือก) ของ $(4)^4$ กราฟ - ทำให้เส้นผ่านศูนย์กลางลดลง $D$ และระยะทางเฉลี่ย $L$.
คำตอบ
การกำหนดค่าจุดยอดต่อไปนี้มีสัญกรณ์ $(3.4.4.4)^1$ และควรให้ตัวอย่างการตอบโต้สำหรับคำถาม 1 (การมีอยู่ของกราฟที่มีขนาดตามอำเภอใจ) และคำถาม 3 (จุดยอด - การขนส่ง)
มีกราฟจำนวนมากเท่านั้นที่ตระหนักถึงการกำหนดค่านี้และกราฟทั้งหมดมีจุดยอดสูงสุด 24 จุด สองอันคือระนาบขอบกราฟของรูปสี่เหลี่ยมขนมเปียกปูน (ซ้าย) และกราฟขอบของรูปสี่เหลี่ยมขนมเปียกปูนหลอกที่เกี่ยวข้องอย่างใกล้ชิด(ขวา) เฉพาะอันแรกเท่านั้นที่เป็นจุดยอด - สกรรมกริยา
กราฟอื่น ๆ ทั้งหมดสามารถหาได้จากสิ่งเหล่านี้โดยการระบุจุดยอด ตัวอย่างเช่นการระบุจุดยอดต่อต้านรูปทรงในกราฟด้านซ้ายจะให้ "รูปทรงหลายเหลี่ยมแบบโปรเจ็กต์"
ฉันเน้นการกำหนดค่าจุดยอดในภาพด้านขวาเนื่องจากไม่ชัดเจนในภาพวาดนี้
ฉันคิดว่านี่คือกราฟทั้งหมดที่มีการกำหนดค่านี้ ฉันอาจจะคิดผิด แต่ไม่มีกราฟแบบนี้ที่มีจุดยอดมากกว่า 24 จุด
โดยทั่วไปคุณอาจสนใจทฤษฎีบทท้องถิ่นจาก
- "The Local Theorem for Monotypic Tilings"โดย Dolbilin และ Schulte
ซึ่งเกี่ยวข้องกับคำถามเมื่อข้อ จำกัด ในท้องถิ่นบางอย่างบ่งบอกถึงความสมมาตรระดับโลก โดยปกติแล้วจะให้ความเป็นเอกลักษณ์และจุดยอด - การเคลื่อนย้าย แต่จะใช้ได้เฉพาะในกรณีที่โทโพโลยีนั้น "เชื่อมต่อกัน" เท่านั้น (สำหรับการเอียงของทรงกลมระนาบยูคลิด / ไฮเพอร์โบลิก แต่ไม่ใช่สำหรับทอรัสดังที่คุณเคยเห็นในคำถามของคุณว่า กราฟไม่ซ้ำกันสำหรับ$(4)^4$).
ในการเริ่มต้นส่วนที่ 3 (ด้านล่างทฤษฎีบท 3.1) พวกเขาระบุว่าการกำหนดค่า $(3.5.5.5)^1$สามารถรับรู้เป็นกราฟไม่มีที่สิ้นสุด แต่ไม่ใช่จุดยอด - สกรรมกริยา ฉันพยายามติดตามการอ้างสิทธิ์นี้ แต่พวกเขาอ้างถึงหนังสือ "Tilings and Patterns" ซึ่งมีการเอียงนับพันอย่างแท้จริงและฉันไม่พบสิ่งที่ต้องการ
สุดท้ายการกำหนดค่าต่อไปนี้ $(3.4.5)^1$ ไม่ควรตระหนักเลย:
หากต้องการดูสิ่งนี้โปรดทราบว่ากราฟต้องมี "ใบหน้าสามเหลี่ยม" (เนื่องจากมีการกำหนดค่า) ขอบทั้งสามของสามเหลี่ยมนั้นจะแบ่งเป็นรูปสี่เหลี่ยมหรือรูปห้าเหลี่ยม Wlog ถือว่าสองขอบใช้ร่วมกันกับรูปสี่เหลี่ยม แต่ขอบทั้งสองนี้มีจุดยอดร่วมกันดังนั้นจุดยอดนี้จึงไม่สามารถเป็นชนิดได้$(3.4.5)^1$.
โดยทั่วไปแล้วการแยกความแตกต่างจากการกำหนดค่าที่ไม่สามารถสร้างได้นั้นค่อนข้างยุ่งยาก ตามหลักทั่วไปแล้วดูเหมือนว่าใบหน้าคี่ก่อให้เกิดปัญหาเช่นเดียวกับที่เคยทำในตัวอย่างก่อนหน้านี้ ดังนั้นเช่นการกำหนดค่า$(\mathbf 5.8.10)^1$ ไม่สามารถดำรงอยู่ได้ด้วยเหตุผลเดียวกันเนื่องจากมีใบหน้าห้าเหลี่ยมที่ล้อมใบหน้าสองประเภทที่แตกต่างกันและไม่มีประเภทใบหน้าซ้ำที่จุดยอด
เนื่องจากคุณพูดถึง (ในความคิดเห็น) ที่คุณสนใจเป็นส่วนใหญ่ $(3.n)^m$ (สมมติ $n\ge 3$, $m\ge 2$):
การกำหนดค่านี้มีอยู่เสมอไม่ซ้ำกันและจุดยอด - ทรานซิทีฟ (สมมติว่า "โทโพโลยีที่เชื่อมต่อกัน" ซึ่งเราสามารถแปลได้ว่า "กราฟเป็นแบบระนาบ")
จำกัด เฉพาะสำหรับ $(3.3)^2$( รูปแปดเหลี่ยม ),$(3.4)^2$( cuboctahedron ) และ$(3.5)^2$( ไอโคซิโดเดคาฮีดรอน). คุณสามารถพิจารณาเป็น "ระนาบ" สำหรับ$\smash{(3.3)^3}$(การปูกระเบื้องสามเหลี่ยม ) และ$\smash{(3.6)^2}$(การปูกระเบื้องสามเหลี่ยม ) และไฮเปอร์โบลิกในกรณีอื่น ๆ ทั้งหมด
ความเป็นเอกลักษณ์และความสมมาตรเป็นผลมาจาก Local Theorem (และทฤษฎีส่วนขยายที่เกี่ยวข้อง) ที่กล่าวถึงก่อนหน้านี้ แต่ในแง่ง่าย: หากคุณพยายามสร้างกราฟด้วยการกำหนดค่าจุดยอดดังกล่าวและคุณเริ่มจากจุดยอดใด ๆ จากนั้นคุณพยายามกำหนดค่าจุดยอดรอบจุดยอดอื่น ๆ ให้เสร็จสมบูรณ์คุณสามารถทำได้ด้วยวิธีที่ไม่ซ้ำใครเท่านั้น (ลองบนกระดาษจริงๆ) เนื่องจากคุณไม่มีทางเลือกในขั้นตอนใด ๆ (จากหลายขั้นตอนที่อาจไม่สิ้นสุด) ผลลัพธ์จึงไม่ซ้ำกัน