GRAPH

Dalam matematika dan ilmu komputer, teori grafik adalah studi tentang grafik, struktur matematis yang digunakan untuk model hubungan berpasangan antara objek dari koleksi tertentu. Sebuah "grafik" dalam konteks ini mengacu pada koleksi simpul atau 'node' dan koleksi tepi yang menghubungkan pasangan vertex. Sebuah grafik dapat diarahkan, yang berarti bahwa tidak ada perbedaan antara dua simpul yang terkait dengan setiap sisi, atau tepi yang dapat diarahkan dari satu titik ke yang lain, lihat grafik (matematika) untuk definisi yang lebih rinci dan untuk variasi lain dalam jenis grafik yang biasanya dipertimbangkan. Grafik dipelajari dalam teori graf tidak harus bingung dengan grafik fungsi atau jenis lain dari grafik.

Dalam arti paling umum istilah, grafik adalah sepasang memerintahkan G = (V, E) terdiri dari seperangkat V simpul atau node bersama-sama dengan E set tepi atau garis, yang 2-elemen himpunan bagian dari V (yaitu, tepi berhubungan dengan dua simpul, dan hubungan ini direpresentasikan sebagai unordered pasangan dari simpul sehubungan dengan tepi tertentu). Untuk menghindari ambiguitas, ini jenis grafik dapat digambarkan tepat seperti yang diarahkan dan sederhana .

Grafik diwakili grafis dengan menggambar sebuah titik atau lingkaran untuk setiap vertex, dan menggambar busur antara dua simpul jika mereka terhubung dengan sebuah sisi. Jika grafik diarahkan, arah ditunjukkan dengan menggambar panah.

Sebuah gambar grafik tidak harus bingung dengan grafik itu sendiri (abstrak non-visual struktur) karena ada beberapa cara untuk struktur gambar grafik. Yang penting adalah simpul yang terhubung ke yang lain dengan berapa banyak tepi dan bukan tata letak yang tepat. Dalam prakteknya sering sulit untuk memutuskan apakah dua gambar mewakili grafik yang sama. Tergantung pada masalah domain beberapa layout mungkin akan lebih cocok dan lebih mudah untuk memahami daripada yang lain.

Multigraph

Sebuah lingkaran adalah tepi (diarahkan atau tidak diarahkan) yang dimulai dan berakhir pada titik yang sama, ini dapat diizinkan atau tidak diizinkan sesuai dengan aplikasi. Dalam konteks ini, sebuah tepi dengan dua ujung yang berbeda yang disebut link.

Istilah " multigraph "umumnya dipahami berarti bahwa beberapa tepi (dan kadang-kadang loop) diperbolehkan. Dimana grafik didefinisikan sehingga memungkinkan loop dan beberapa tepi, multigraph sering kali didefinisikan berarti grafik tanpa loop, Namun, di mana grafik didefinisikan sehingga loop melarang dan beberapa tepi, istilah ini sering didefinisikan berarti "grafik" yang dapat memiliki kedua sisi ganda dan loop, meskipun banyak menggunakan istilah " pseudograph "untuk makna ini.

grafik Sederhana

Sebagai lawan multigraph, sebuah grafik sederhana adalah sebuah grafik diarahkan yang tidak memiliki loop dan tidak lebih dari satu tepi antara dua simpul yang berbeda. Dalam sebuah grafik sederhana tepi grafik bentuk menetapkan (bukan multiset) dan tepi masing-masing sepasang simpul berbeda. Dalam sebuah grafik sederhana dengan n simpul simpul setiap memiliki gelar yang kurang dari n (yang sebaliknya, bagaimanapun, adalah tidak benar - terdapat non-grafik sederhana dengan simpul n di mana setiap simpul memiliki derajat lebih kecil dari n).