Menghasilkan grafik ketebalan

Biarkan . Saya perlu membuat grafik sederhana dengan ketebalan sedemikian sehingga himpunan semua sepeda membentuk penutup tepi ganda (yaitu, setiap tepi dibagi dengan tepat dua sepeda), dan sedemikian rupa sehingga persimpangan dari dua sepeda bisa berupa simpul, tepi, atau kosong. Grafik yang dihasilkan harus besar secara sewenang-wenang. $g\geq 3$ $G$ $g$ $g$ $G$ $g$ $g$

Metode generasi harus memiliki keacakan, tetapi tidak dalam arti sepele. Saya ingin dapat memperoleh grafik yang cukup rumit. Sebagai contoh, bayangkan sebuah kotak persegi panjang di pesawat. Jika kami mengidentifikasi sisi berlawanan dari persegi panjang pembatas, kami memperoleh grafik yang memenuhi semua persyaratan di atas untuk . Saya akan memenuhi syarat grafik ini sebagai sederhana. $n\times m$ $g=4$

Apakah ada metode seperti itu?

Setiap referensi untuk masalah yang sama juga dihargai.

ds.algorithms reference-request graph-theory co.combinatorics pseudorandom-generators becko
sumber

Jadi Anda ingin sepeda

menjadi wajah dari beberapa polyhedral embedding grafik ke permukaan tertentu? (Penyisipan grafik adalah "polyhedral" jika setiap wajah penyematan adalah disk, dan dua wajah apa pun memiliki simpul yang sama, berbagi tepi yang sama, atau tidak berpotongan sama sekali.)

g

$g$

Jeffε

@ Jɛ ﬀ E Ya. Jika semua

sepeda dijamin menjadi wajah, dan semua wajah dijamin menjadi

sepeda, maka itu adalah deskripsi yang setara.

g

$g$

g

$g$

becko

@ Jɛ ﬀ E Apakah Anda tahu di mana saya dapat menemukan grafik 4-reguler yang berbeda dan embeddings polyhedral mereka? Mereka tidak harus berupa grafik yang besar, tapi saya ingin melihat grafik lain yang memenuhi properti yang saya minta selain yang saya sebutkan. Saya juga tahu bahwa menentukan embeddability polyhedral adalah NP-lengkap berkat jawaban ini . Terlepas dari itu, saya juga ingin tahu tentang algoritma yang menemukan embed polyhedral jika ada. Apakah Anda tahu ada sumber daya / kertas / ... yang menjelaskan algoritma seperti itu?

becko

apakah ada tautan antara 4 grafik reguler dan pernikahan polihedral? apakah seseorang memiliki deskripsi tentang itu? tahun lalu mencari makalah tentang pembuatan grafik reguler secara acak, ada beberapa, karena itu jika Anda dapat mengulangi pertanyaan ini dalam bentuk grafik reguler, ini mungkin mengarah pada lebih banyak kemungkinan.

vzn

@ vzn Misalkan saya memiliki embed polyhedral seperti yang disarankan oleh Jeff. Semua wajah yang

-cycles. Grafik ganda yang diperoleh dari penyematan ini adalah

regular. Mungkin ini bisa dibalik: mulailah dengan grafik

regular dan temukan gandanya. Itulah yang ada dalam pikiran saya.

g

$g$

g

$g$

g

$g$

becko

Ide setengah matang saya agak terlalu ambisius. Saya memasukkannya di bawah ini untuk referensi, tetapi kondisi jarak yang saya tentukan sebenarnya tidak cukup untuk menjamin ketebalan yang besar.

Ada peta permukaan sangat simetris yang sewenang-wenang besar dengan ketebalan besar, tetapi bukti keberadaan yang dipublikasikan sebagian besar didasarkan pada teori kelompok daripada topologi atau geometri per se.

$g$ $d$ $r$ $1/g + 1/d < 1/2$ $g$ $d$ $r$ $r$ $g$

Roman Nedela dan Martin Škoviera. Peta reguler pada permukaan dengan lebar planar besar. European J. Combinatorics 22 (2): 243--262, 2001.
Jozef Širáň. Representasi kelompok segitiga dan konstruksi peta reguler. Proc London Math. Soc. 82 (3): 513-532, 2001.

Setelah Anda memiliki satu peta permukaan seperti itu, peta yang lebih besar dengan ketebalan dan derajat yang sama dapat dihasilkan dengan membangun ruang penutup.

$G$

$G$ $g$
$G$ $G$ $g$ $g$ $G$
$G$ ~~$G$ $g$~~

$g$

$G'$ $g$ $G$ $G$ $G'$ $G'$ $g$

$G$ $d$ $d$ $g$ $1/d + 1/g < 1/2$

Jeffε
sumber

Juga, grafik yang Anda dapatkan dari konstruksi ini adalah ekspander.

Jeffε

g

$g$

Apa itu grafik expander ?

becko

@becko, Anda harus Google sebelum bertanya :) en.wikipedia.org/wiki/Expander_graph

Kaveh

@ Kaveh Ok. Maaf saya melewatkan itu :)

becko

Menghasilkan grafik ketebalan

Jawaban: