Friday, January 18, 2013

PETERSEN GRAPH

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


Pentagon, USA.




8 comments:

  1. APAKAH ANDA TERMASUK DALAM KATEGORI INI;
    1: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

    ReplyDelete
    Replies
    1. 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.

      Delete
  2. 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)







    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)






    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)


    ReplyDelete
    Replies
    1. 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

      Delete
  3. SAYA 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

    ReplyDelete
  4. 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
    • لالله�أشهدألاإله إلاالله،وأشهدأن محمدرسوالله صلى الله عليه وسلموعليكومالله�أشهدألاإله






    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
    • لالله�أشهدألاإله إلاالله،وأشهدأن محمدرسوالله صلى الله عليه وسلموعليكومالله�أشهدألاإله

    ReplyDelete
  5. 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.

    ReplyDelete
  6. BAGI 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.

    BAGI 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.

    ReplyDelete