Teori Graf


dalam teori grafik, sebuah jejak Euler adalah jejak dalam grafik yang dilihat setiap sisi tepat satu kali. Demikian pula, sebuah sirkuit Euler atau siklus Euler adalah jejak Eulerian yang dimulai dan berakhir pada titik yang sama. Mereka pertama kali dibahas oleh Leonhard Euler sementara memecahkan Tujuh Jembatan terkenal masalah Königsberg pada tahun 1736. Masalah matematis dapat dinyatakan seperti ini:

Mengingat grafik di sebelah kanan, apakah mungkin untuk membangun jalur (atau siklus, yaitu jalan dimulai dan berakhir pada titik yang sama) yang dilihat setiap sisi tepat satu kali?

Euler membuktikan bahwa kondisi yang diperlukan untuk keberadaan sirkuit Euler adalah bahwa semua titik dalam grafik memiliki gelar bahkan, dan menyatakan tanpa bukti bahwa grafik berhubungan dengan semua titik bahkan gelar memiliki sirkuit Euler. Bukti lengkap pertama dari klaim ini terakhir diterbitkan pada tahun 1873 oleh Carl Hierholzer. [1]

Grafik Eulerian Istilah memiliki dua makna umum dalam teori graph. Satu makna adalah grafik dengan sirkuit Euler, dan yang lainnya adalah grafik dengan setiap simpul derajat bahkan. Definisi ini bertepatan untuk grafik tersambung. [2]

Untuk keberadaan jalan Eulerian perlu bahwa tidak lebih dari dua titik memiliki gelar aneh, ini berarti grafik Königsberg tidak Euler. Jika tidak ada titik derajat aneh, semua jejak Euler adalah sirkuit. Jika terdapat tepat dua simpul derajat aneh, semua jejak Eulerian mulai dari salah satu dari mereka dan berakhir pada yang lain. Kadang-kadang grafik yang memiliki jejak Eulerian tapi bukan sirkuit Euler disebut semi-Euler.

Sebuah jejak Euler, [3] atau Euler berjalan dalam grafik tak berarah adalah jalan yang menggunakan setiap sisi tepat satu kali. Apabila jalan ada, grafik disebut traversable atau semi-Euler. [4]

Siklus Euler, [3] sirkuit Euler atau wisata Euler dalam graf tak berarah adalah siklus yang menggunakan setiap sisi tepat satu kali. Apabila siklus ada, grafik disebut unicursal. [5] Sementara grafik tersebut grafik Euler, tidak setiap grafik Euler memiliki siklus Euler.

Untuk jalur grafik diarahkan harus diganti dengan jalan diarahkan dan siklus dengan siklus diarahkan.

Definisi dan sifat Euler, siklus jalur dan grafik tersebut berlaku untuk multigraphs juga.

* Sebuah grafik yang terhubung tak berarah Euler jika dan hanya jika setiap simpul graf memiliki gelar bahkan.
* Sebuah graf tak berarah adalah Euler jika sudah terhubung dan dapat diuraikan menjadi siklus tepi-menguraikan.
* Jika suatu graf tak berarah G adalah Eulerian lalu garis grafiknya L (G) Eulerian juga.
* Sebuah grafik diarahkan adalah Euler jika sangat terhubung dan setiap simpul yang sama dalam derajat dan derajat keluar.
* Sebuah grafik diarahkan adalah Euler jika sangat berhubungan dan dapat diuraikan menjadi siklus diarahkan tepi-menguraikan.
* Sebuah jejak Eulerian ada dalam grafik diarahkan jika dan hanya jika mendasari grafik grafik itu tak berarah tersambung, paling tidak satu titik telah keluar gelar-dalam derajat = 1, paling tidak satu simpul memiliki derajat derajat-out = 1 dan setiap vertex lain telah sama dalam derajat dan derajat keluar.
* Sebuah graf tak berarah adalah traversable jika terhubung dan paling banyak dua titik dalam grafik adalah derajat ganjil.

http://mathworld.wolfram.com/EulerGraph.html

http://www.informatika.org/~rinaldi/Matdis/2006…/Makalah0607-130.pdf

http://www.freewebs.com/infoitn/…/graf/lintasan%20euler,hamilton.docx

http://en.wikipedia.org/wiki/Eulerian_path

Beli T-Shirt, Raglan dan Kids T-Shirt Original Ocean Seven

  1. T-Shirt, Raglan dan Kids T-Shirt Anime, Manga, Gamers dan Cartoon World (OceanSeven)
  2. T-Shirt, Raglan dan Kids T-Shirt Footbal Series (OceanSeven)
  3. T-Shirt, Raglan dan Kids T-Shirt Music Series (OceanSeven)
  4. T-Shirt, Raglan dan Kids T-Shirt OceanSeven – Custom dan Basic Tees (OceanSeven)
  5. T-Shirt, Raglan dan Kids T-Shirt OceanSeven -Kids Collections (OceanSeven)
  6. T-Shirt, Raglan dan Kids T-Shirt OceanSeven -Signature Serues (OceanSeven)
  7. T-Shirt, Raglan dan Kids T-Shirt  Social Media dan Photography (OceanSeven)
  8. T-Shirt, Raglan dan Kids T-Shirt Sport, Automotive dan Adventure (OceanSeven)
  9. T-Shirt, Raglan dan Kids T-Shirt Superheroes dan Movies (OceanSeven)

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s