The Petersen graph
is an undirected graph with 10 vertices and 15 edges. It
is a small graph that serves as a useful example and counterexample for many
problems in graph theory. The Petersen graph is named for Julius
Petersen, who in
1898 constructed it to be the smallest bridgeless cubic
graph with no
three-edge-coloring. Although the graph is generally credited to Petersen, it
had in fact first appeared 12 years earlier, in 1886. Donald
Knuth states
that the Petersen graph is "a remarkable configuration that serves as a
counterexample to many optimistic predictions about what might be true for
graphs in general."
The Petersen graph is the complement of the line
graph of K5.
It is also the Kneser graph KG5,2; this means that it has one vertex
for each 2-element subset of a 5-element set, and two vertices are connected by
an edge if and only if the corresponding 2-element subsets are disjoint from
each other. As a Kneser graph of the form KG2n − 1,n
− 1 it is an example of an odd
graph. Geometrically,
the Petersen graph is the graph formed by the vertices and edges of the hemi-dodecahedron, that is, a dodecahedron with opposite points, lines and
faces identified together.
The Petersen graph is nonplanar. Any nonplanar graph has as minors either the complete
graph K5,
or the complete bipartite graph K3,3, but the Petersen graph
has both as minors. The K5 minor can be formed by contracting
the edges of a perfect matching, for instance the five short edges in the first
picture. The K3,3 minor can be formed by deleting one vertex
(for instance the central vertex of the 3-symmetric drawing) and contracting an
edge incident to each neighbor of the deleted vertex.
The
Petersen graph has crossing
number 2.
The most common and symmetric plane drawing of
the Petersen graph, as a pentagram within a pentagon, has five crossings. However,
this is not the best drawing for minimizing crossings; there exists another
drawing (shown in the figure) with only two crossings. Thus, the Petersen graph
has crossing number 2. On a torus the Petersen graph can be drawn without edge
crossings; it therefore has orientable genus 1.
The
Petersen graph is a unit
distance graph:
it can be drawn in the plane with each edge having unit length.
The Petersen graph can also be drawn (with crossings) in the
plane in such a way that all the edges have equal length. That is, it is a unit
distance graph.
The
simplest non-orientable surface on which the Petersen graph can be
embedded without crossings is the projective
plane. This is
the embedding given by the hemi-dodecahedron construction of the Petersen graph.
The projective plane embedding can also be formed from the standard pentagonal
drawing of the Petersen graph by placing a cross-cap within the five-point star at the
center of the drawing, and routing the star edges through this cross-cap; the
resulting drawing has six pentagonal faces. This construction forms a regular map and shows that the Petersen graph
has non-orientable genus 1.
The Petersen graph is strongly regular. It is also symmetric, meaning that it is edge transitive and vertex transitive. More strongly, it is
3-arc-transitive: every directed three-edge path in the Petersen graph can be
transformed into every other such path by a symmetry of the graph. It is one of
only 13 cubic distance-regular
graphs.
The automorphism group of the Petersen graph is the symmetric
group S5;
the action of S5 on the Petersen graph follows from its
construction as a Kneser graph. Every homomorphism of the Petersen graph to itself
that doesn't identify adjacent vertices is an automorphism. As shown in the
figures, the drawings of the Petersen graph may exhibit five-way or three-way
symmetry, but it is not possible to draw the Petersen graph in the plane in
such a way that the drawing exhibits the full symmetry group of the graph. Despite
its high degree of symmetry, the Petersen graph is not a Cayley
graph. It is
the smallest vertex-transitive graph that is not a Cayley graph.
Application of Petersen graph
Hamiltonian paths and cycles
The Petersen graph is hypo-Hamiltonian: by deleting any
vertex, such as the center vertex in the drawing, the remaining graph is
Hamiltonian. In addition, this drawing shows symmetry of order three, in
contrast to the symmetry of order five visible in the first drawing above.
The Petersen graph has a Hamiltonian
path but no Hamiltonian cycle. It is the
smallest bridgeless cubic graph with no Hamiltonian cycle. It is hypohamiltonian, meaning that although it has no
Hamiltonian cycle, deleting any vertex makes it Hamiltonian, and is the
smallest hypohamiltonian graph.
As
a finite connected vertex-transitive graph that does not have a Hamiltonian
cycle, the Petersen graph is a counterexample to a variant of the Lovász conjecture, but the canonical formulation of the conjecture asks for a
Hamiltonian path and is verified by the Petersen graph.
Only five vertex-transitive graphs with no Hamiltonian
cycles are known: the complete
graph K2,
the Petersen graph, the Coxeter
graph and two
graphs derived from the Petersen and Coxeter graphs by replacing each vertex
with a triangle. If G is a 2-connected, r-regular graph with at
most 3r + 1 vertices, then G is Hamiltonian or G
is the Petersen graph.
To see that the Petersen graph has no Hamiltonian cycle C,
we describe the ten-vertex 3-regular graphs that do have a Hamiltonian cycle and show that none of them
is the Petersen graph, by finding a cycle in each of them that is shorter than
any cycle in the Petersen graph. Any ten-vertex Hamiltonian 3-regular graph
consists of a ten-vertex cycle C plus five chords. If any chord connects
two vertices at distance two or three along C from each other, the graph
has a 3-cycle or 4-cycle, and therefore cannot be the Petersen graph. If two
chords connect opposite vertices of C to vertices at distance four along
C, there is again a 4-cycle. The only remaining case is a Möbius
ladder formed by
connecting each pair of opposite vertices by a chord, which again has a
4-cycle. Since the Petersen graph has girth five, it cannot be formed in this
way and has no Hamiltonian cycle.
Example of Hamiltonian paths and cycles
APAKAH ANDA TERMASUK DALAM KATEGORI INI;
ReplyDelete1:DILILIT HUTANG
2:SELALU KALAH DALAM BERMAIN TOGEL
3:BUTUH MODAL DALAM BUKA USAHA
4:PENGLARIS USAHA
5:BARANG BERHARGA ANDA SUDAH HABIS
BUAT JUDI TOGEL
ANDA SUDAH KEMANA MANA TAPI TIDAK MENDAPATKAN
SOLUSI YANG TEPAT,JANGAN ANDA RAGU
UNTUK MENGHUBUNGI LANGSUN MBAH SARTO
DI 082=378=607=111 DAN MUDAH MUDAHAN
INI SUDAH BISA MENJADI SOLUSI YANG SANGAT TEPAT
KARNA RAMALAN MBAH SARTO
MEMAN MEMILIKI RAMALAN
“GHOIB” YANG DIJAMIN
100% TEMBUS,ADAPUN RAMALAN INI DIDAPAT
MELALUI “RITUAL KHUSUS”
DAN RAMALAN INI TELAH
TERBUKTI SELAMA 3 TAHUN
TIDAK PERNAH GAGAL DAN
SELALU TEMBUS,UNTUK MENDAPATKAN RAMALAN
TEMBUS MBAH SARTO,ANDA HARUS
MENGIRIM PULSA DULU SEBANYAK 100 RIBU
UNTUK MENJADI MEMBER DAN ANDA AKAN
DIBANTU DALAM 4X PUTARAN.
JANGAN ANDA
RAGU SOAL MASALAH
ANKA YANG AKAN
DIBERIKAN SAMA MBAH SARTO KARNA ANKA
YANG ANDA DAPATKAN
ADALAH ANKA RITUAL YANG
DIJAMIN 100% TEMBUS DAN
SUDAH BANYAK ORANG
YANG DIBANTUH SAMA MBAH
SARTO..DAN ALHAMDULILLAH
MEREKA SEMUA SUDAH
BERHASI… BETAPA
INDAHNYA BILA SALING
BERBAGI,BETAPA BAHAGIA
BILA MENJADI YG TERBAIK,BETAPA GEMBIRA BILA KITA
JP BARENG HANYA SALING
BERBAGI BISA MENCAPAI
KEBERHASILAN,DAN SILAHKAN
MENUJU HARI YG SUDAH
TERSEDIA,,JIKA ANDA INGIN MENCAPAI KEBERHASILAN
SEPERTI SAYA SILAHKAN HUBUNGI
MBAH SARTO DI 082=378=607=111
Dukun sakti mantra Guna sangat di kenal dan diakui di tengah kalangan masayarakat, yang mempunyai 1001 Ahli Seperti : Cepat KAYA ( Pesugihan ) Melumpuhkan Pesaingan Bisnis Mempunyai barang antik, bisa membuat tubuh jadi kebal Dan minyak gaib, yang biasa di sebut, minyak bintang Mengobati Segalah Penyakit Yang Berupa ILMU HITAM ( DLL ) Tuntaskan Masalah Yg Membebani anda Karena Tampah Usaha Tujuan Tak akan Tercapai Mohon Perhatian..!! Sehubungan dengan banyaknya pihak-pihak yang tidak bertanggung jawab yg mengatasnamakan aki & mengeruk keuntungan Pribadi dengan menjual nama . maka dengan ini aki beritahukan kepada semua Pasien & calon pasien baru bahwa NO HP YANG ASLI ADALAH KYAI DARSO 082-361-234-469 yang asli adalah yg terterah diatas , agar lebih afdol kirannya selain menelpon langsung, anda diharuskan juga mengirim maksud & tujuan ke Nomor telpon di bawa ini,082-361-234-469 terimahkasii.
DeleteDemi ALLAH saya benar-benar yakin dan percaya angka goib KI SAMJOYO telah saya buktikan juga kemarin saya dapat,awalnya saya ragu tapi saya mencoba meghubungi lgi dan meminta angka juga sama KI SAMJOYO 3D SGP akhirnya tembus juga usaha 85 juta, sekarang sya sudah buka toko pakaian dan melunasi semua utang saya yg ada di bank, trimaksih KI SAMJOYO jasamu takkan kami lupakan, ini bukan janji tpi bukti silahkan bergbung dengan KI SAMJOYO DI (082 344 448 268)
ReplyDeleteDemi ALLAH saya benar-benar yakin dan percaya angka goib KI SAMJOYO telah saya buktikan juga kemarin saya dapat,awalnya saya ragu tapi saya mencoba meghubungi lgi dan meminta angka juga sama KI SAMJOYO 3D SGP akhirnya tembus juga usaha 85 juta, sekarang sya sudah buka toko pakaian dan melunasi semua utang saya yg ada di bank, trimaksih KI SAMJOYO jasamu takkan kami lupakan, ini bukan janji tpi bukti silahkan bergbung dengan KI SAMJOYO DI (082 344 448 268)
Demi ALLAH saya benar-benar yakin dan percaya angka goib KI SAMJOYO telah saya buktikan juga kemarin saya dapat,awalnya saya ragu tapi saya mencoba meghubungi lgi dan meminta angka juga sama KI SAMJOYO 3D SGP akhirnya tembus juga usaha 85 juta, sekarang sya sudah buka toko pakaian dan melunasi semua utang saya yg ada di bank, trimaksih KI SAMJOYO jasamu takkan kami lupakan, ini bukan janji tpi bukti silahkan bergbung dengan KI SAMJOYO DI (082 344 448 268)
SAYA INGIN BERBAGI CERITA KEPADA SEMUA ORANG BAHWA MUNKIN AKU ADALAH ORANG YANG PALING MISKIN DIDUNIA DAN SAYA HIDUP BERSAMA .SUAMI DAN 3 BUAH HATI SAYA SELAMA 10 TAHUN DAN 10 TAHUN ITU KAMI TIDAK PERNAH MERASAKAN YANG NAMANYA KEMEWAHAN,,SETIAP HARI SAYA SELALU MEMBANTIN TULANG BERSAMA,ISTRI SAYA UNTUK KELUARGA SAYA NAMUN ITU SEMUA TIDAK PERNAH CUKUP UNTUK KEBUTUHAN HIDUP KELUARGA SAYA..AKHIRNYA AKU PILIH JALAN TOGEL INI DAN SUDAH BANYAK PARA NORMALYANG SAYA HUBUNGI NAMUN ITU SEMUA TIDAK PERNAH MEMBAWAKAN HASIL DAN DISITULAH AKU SEMPAT PUTUS ASA AKHIRNYA ADA SEORANG TEMAN YANG MEMBERIKAN NOMOR,AKI SANTANU ,, SAYA PIKIR TIDAK ADA SALAHNYA JUGA SAYA COBA LAGI UNTUK MENGHUBUNGI,AKI SANTANU. DAN AKHIRNYA,AKI SANTANU, MEMBERIKAN ANGKA GHOIBNYA, ,4D… DAN ALHAMDULILLAH BERHASIL..KINI SAYA SANGAT BERSYUKUR MELIHAT KEHIDUPAN KELUARGA SAYA SUDAH JAUH LEBIH BAIK DARI SEBELUMNYA,DAN TANDA TERIMAH KASIH SAYA KEPADA .AKI SETIAP SAYA DAPAT RUANGAN PASTI SAYA BERKOMENTAR TENTAN.AKI BAGI ANDA YANG INGIN MERUBA NASIB SEPERTI SAYA SILAHKAN HUBUNGI AKI SANTANU DI:082 317 877 775
DeleteSAYA BENAR BENAR TIDAK PERCAYA DAN HAMPIR PINSANG KARNA ANKA YANG DIBERIKAN OLEH MBAH SARTO TERNYATA TEMBUS,AWALNYA SAYA COBA COBA MENELPON DAN SAYA MEMBERITAHUKAN SEMUA KELUHAN SAYA KEPADA MBAH SARTO,,ALHAMDULILLAH MBAH SARTO TELAH MEMBERIKAN SAYA SOLUSI YANG SANGAT TEPAT DAN DIA MEMBERIKAN ANKA YANG BEGITU TEPAT..,MULANYA SAYA RAGU TAPI DENGAN PENUH SEMANGAT ANKA YG DIBERIKAN MBAH SARTO ITU ITU SAYA KALI 100 LEMBAR DAN SYUKUR ALHAMDULILLAH BERHASIL,SESEKALI LAGI MAKASIH BANYAK YAA MBAH,SAYA TIDAK AKAN LUPA BANTUAN DAN BUDI BAIK MBAH SARTO,JIKA ANDA INGIN SEPERTI SAYA SILAHKAN HUBUNGI MBAH SARTO DI 082=378=607=111
ReplyDeletesaya pendatang baru di ROOM ini ingin mengucapkan terima kasih banyak kepada MBAH RINGGO , berkat bantuan No togel 4Dnya2199 yang MBAH berikan ternyata benar2 tembus, saya tidak tau harus berbuat apa untuk membalas kebaikan MBAH,awalnya saya kurang yakin dengan angka yang MBAH berikan, tapi ternyata alhamdulillah saya menang 4D lagi dan sionya, sudah berapa banyak peramal yang saya hubungi tidak ada satupun yang tembus malahan hutang-hutang saya bertambah banyak,kini kehidupan saya jauh lebih sukses dari pada sebelumnya ini semua berkat bantuan MBAH RINGGO,bagi teman-teman pembeli kupon putih yang tidak pernah merasakan kemenangan 4D silahkan hubungi MBAH RINGGO di nomor : 0852-0521-3777- dan angka yang di berikan MBAH RINGGO dalam7 putaran ini tidak perna meleset,anda jangan mudah tergiur dengan janji-janji saatnya kita perlu bukti hanya MBAH RINGGO yang menjamin 100% kemenangan.kalau mau bukti hubungi sekarang. SEMOGA.JP
ReplyDelete• لالله�أشهدألاإله إلاالله،وأشهدأن محمدرسوالله صلى الله عليه وسلموعليكومالله�أشهدألاإله
saya pendatang baru di ROOM ini ingin mengucapkan terima kasih banyak kepada MBAH RINGGO , berkat bantuan No togel 4Dnya2199 yang MBAH berikan ternyata benar2 tembus, saya tidak tau harus berbuat apa untuk membalas kebaikan MBAH,awalnya saya kurang yakin dengan angka yang MBAH berikan, tapi ternyata alhamdulillah saya menang 4D lagi dan sionya, sudah berapa banyak peramal yang saya hubungi tidak ada satupun yang tembus malahan hutang-hutang saya bertambah banyak,kini kehidupan saya jauh lebih sukses dari pada sebelumnya ini semua berkat bantuan MBAH RINGGO,bagi teman-teman pembeli kupon putih yang tidak pernah merasakan kemenangan 4D silahkan hubungi MBAH RINGGO di nomor : 0852-0521-3777- dan angka yang di berikan MBAH RINGGO dalam7 putaran ini tidak perna meleset,anda jangan mudah tergiur dengan janji-janji saatnya kita perlu bukti hanya MBAH RINGGO yang menjamin 100% kemenangan.kalau mau bukti hubungi sekarang. SEMOGA.JP
• لالله�أشهدألاإله إلاالله،وأشهدأن محمدرسوالله صلى الله عليه وسلموعليكومالله�أشهدألاإله
Hal yang tidak pernah terbayankan kini menjadi kenyataan dengan keluargaku,,,untuk MBAH SARTO kami ucapkan banyak terimakasih karna berkat bantuannya ALHAMDULILLAH keluarga kami bisa lepas dari hutang dan masalah,karna nomor “GHOIB”untuk pasangf togel,hasil ritual MBAH SARTO meman benar2 merubah nasib kami hanya sekejap,dan disitulah aku berkesempatan kumpulkan uang untuk buka usaha kembali,karna baik rumah sudah disita,,warung makan jg sudah bangkrut,,tapi itu semua aku masih tetap bertahan hidup dengan anak istriku,,walau cuma kontrak tapi aku tetap bersabar dan akhirnya MBAH SARTO lah yang bisa merubah nasib kami..MBAH SARTO orang paling bersejarah kepada keluarga saya…!!! Kepada teman2 yang di lilit hutang dan ingin merubah nasib baik dari pada sekaran HBG: 082=378=607=111 MBAH SARTO,dengan penuh harapan INSYAH ALLAH pasti tercapai.
ReplyDeleteBAGI TEMAN-TEMAN YANG SELALU KALAH DALAM PERMAINAN TOGEL DAN INGIN MERASAKAN YANG NAMANYA KEMENANGAN SILAHKAN HUBUNGI MBAH SARTO DI 082=378=607=111 JANGAN ANDA RAGU UNTUK MENCOBA DULU DAN YANG PENTING KITA BERANI MELANGKAH KARNA KITA CUMA MANUSIA BIASA YANG HANYA MAMPU BERUSAHA DAN BERDOA,INGAT SIAPA YANG BERSUNGGUH-SUNGGUH PASTI AKAN MENDAPATKANNYA DAN ALLAH TIDAK MERUBAH NASIB KITA KALAU BUKAN KITA SENDIRI YANG MERUBAHNYA…KALAU KITA BERSUNGGUH-SUNGGUH DAN NIAT KITA BAIK INSYA ALLAH OTOMATIS HASILNYA KITA AKAN RASAKAN SENDIRI,KARNA SAYA SENDIRI SUDAH MERASAKANNYA DAN SUDAH MELIHAT BUKTINYA KALAU ANKA DARI HASIL RITUAL DARI MBAH SARTO BISA MEMBAWA SAYA JAUH LEBIH SUKSES DARI SEBELUMNYA DAN SILAHKAN ANDA MEMBUKTIKAN SENDIRI.
ReplyDeleteBAGI TEMAN-TEMAN YANG SELALU KALAH DALAM PERMAINAN TOGEL DAN INGIN MERASAKAN YANG NAMANYA KEMENANGAN SILAHKAN HUBUNGI MBAH SARTO DI 082=378=607=111 JANGAN ANDA RAGU UNTUK MENCOBA DULU DAN YANG PENTING KITA BERANI MELANGKAH KARNA KITA CUMA MANUSIA BIASA YANG HANYA MAMPU BERUSAHA DAN BERDOA,INGAT SIAPA YANG BERSUNGGUH-SUNGGUH PASTI AKAN MENDAPATKANNYA DAN ALLAH TIDAK MERUBAH NASIB KITA KALAU BUKAN KITA SENDIRI YANG MERUBAHNYA…KALAU KITA BERSUNGGUH-SUNGGUH DAN NIAT KITA BAIK INSYA ALLAH OTOMATIS HASILNYA KITA AKAN RASAKAN SENDIRI,KARNA SAYA SENDIRI SUDAH MERASAKANNYA DAN SUDAH MELIHAT BUKTINYA KALAU ANKA DARI HASIL RITUAL DARI MBAH SARTO BISA MEMBAWA SAYA JAUH LEBIH SUKSES DARI SEBELUMNYA DAN SILAHKAN ANDA MEMBUKTIKAN SENDIRI.