Penerapan teori grafik dalam ilmu komputer

11

Saya seorang siswa CS. Kami melakukan teori grafik dalam satu saja. Saya menemukan itu menarik.

Apa aplikasi nyata dari teori grafik di bidang ilmu komputer?

Sebagai contoh, saya menemukan bahwa beberapa konsep dalam teori grafik dapat digunakan untuk merancang jaringan. Apa aplikasi serupa lainnya?

graph-theory co.combinatorics big-list application-of-theory nbro
sumber
1
ini bisa menjadi daftar yang sangat panjang. Saya sedang berpikir CW?
Suresh Venkat
4
Ini sepertinya terlalu umum bahkan untuk CW. Teori grafik ada di mana-mana dalam TCS.
Huck Bennett
30
Meminta topik dalam CS yang tidak menggunakan grafik mungkin menghasilkan daftar yang lebih pendek.
Raphael
1
@ Peedarpk: Jika Anda mengikuti kelas pada teori grafik di CS cursus, mengapa Anda tidak bertanya kepada profesor?
Anthony Labarre
3
Sungguh, bisakah kita menutup ini sekarang? Jawaban untuk pertanyaan ini ada di wikipedia ( en.wikipedia.org/wiki/Graph_theory#Applications ) atau di buku teks sarjana pengantar apa pun.
RJK

Jawaban:

12

Ini sama sekali bukan jawaban yang pasti, dan saya tidak bermaksud demikian.

Banyak masalah yang menarik bagi para ilmuwan komputer dapat diungkap sebagai masalah grafik, dan sebagai akibatnya teori grafik muncul cukup banyak dalam teori kompleksitas. Upaya komputasi diperlukan untuk menentukan di mana dua grafik isomorfis, misalnya, saat ini menjadi topik yang banyak diminati dalam teori kompleksitas (tidak diketahui sebagai NP-lengkap atau terkandung dalam P, BPP atau BQP, tetapi jelas dalam NP) . Grafik non-isomorfisme, di sisi lain, memiliki bukti nol-pengetahuan yang sangat bagus (bidang studi lain dalam teori kompleksitas). Banyak kelas kompleksitas memiliki masalah grafik yang lengkap untuk kelas itu (dalam beberapa pengurangan).

Namun bukan hanya teori kompleksitas yang memanfaatkan teori grafik. Seperti yang dapat Anda lihat dari beberapa jawaban lain, ada cukup banyak masalah di mana bahasa teori graf paling tepat. Ada banyak aplikasi yang jauh untuk memberikan daftar difinitif, jadi sebagai gantinya saya akan meninggalkan Anda dengan sebuah contoh bagaimana teori grafik memainkan peran mendasar dalam bidang penelitian saya sendiri.

Perhitungan kuantum berbasis pengukuran adalah model perhitungan yang tidak memiliki padanan di dunia klasik. Dalam model ini, perhitungan didorong dengan melakukan pengukuran pada kelas khusus keadaan kuantum. Keadaan ini dikenal sebagai keadaan grafik, karena setiap keadaan dapat diidentifikasi secara unik dengan grafik tidak terarah dengan sejumlah simpul yang sama dengan jumlah qubit dalam keadaan grafik. Namun, hubungan dengan teori grafik ini lebih dari kebetulan. Kita tahu bahwa kelas pengukuran yang penting (pengukuran berbasis Pauli jika Anda tertarik) memetakan status grafik yang mendasari ke status grafik baru pada satu kurang qubit, dan aturan-aturan yang dengannya hal ini terjadi dipahami dengan baik. Lebih lanjut, properti dari keluarga grafik dasar (aliran dan g-aliran) ditentukan sepenuhnya apakah mendukung komputasi universal. Akhirnya, untuk setiap grafik G 'yang dapat dicapai dari grafik lain G dengan urutan sewenang-wenang yang melengkapi tepi-tepi lingkungan sebuah simpul dapat dicapai dengan operasi qubit tunggal saja, dan dengan demikian sama kuatnya sebagai sumber daya untuk perhitungan. Ini menarik karena jumlah tepi, maksimum titik sudut, dll dapat berubah secara drastis.

Joe Fitzsimons
sumber
Jawaban bagus untuk apa yang tidak mungkin ditanyakan oleh OP! Tetapi secara topikal, mengapa kita tidak melupakan versi asli (buruk) dari pertanyaan dan berpura-pura kita bermain Jeopardy: "Apa intuisi di balik kemunculan grafik di hampir semua sub-disiplin ilmu komputer teoretis?"
RJK
@RJK: Mungkin saya seharusnya membaca pertanyaan itu lebih hati-hati, tapi saya pikir ini setidaknya menarik bagi orang yang mengajukan pertanyaan.
Joe Fitzsimons
Tidak tidak, ini jawaban yang bagus.
Montagist
5

Aplikasi teori grafik berlimpah dalam ilmu komputer dan dalam kehidupan sehari-hari:

  • Menemukan rute terpendek dalam sistem navigasi mobil
  • Mesin pencari menggunakan algoritma peringkat berdasarkan teori grafik
  • Mengoptimalkan tabel waktu untuk sekolah atau universitas
  • Analisis jejaring sosial
  • Mengoptimalkan pemanfaatan sistem kereta api
  • Compiler menggunakan algoritma pewarnaan untuk menetapkan register ke variabel
  • Perencanaan jalur dalam robotika
Volker Turau
sumber
3

Teori Grafik memiliki berbagai aplikasi. Aplikasi favorit saya adalah di:

  • Jaringan Skala Besar
  • Komputasi Sosial
  • Bio-informatika
Nikhil
sumber
2

Jaringan pemodelan dilakukan dengan menggunakan grafik. Misalnya, jika Anda perlu mempelajari penyiaran atau multicasting dalam jenis topologi jaringan tertentu, Anda akan menggunakan grafik untuk memodelkan jaringan. Sebagai contoh:

  • hypergraphs
  • grafik lengkap
  • grafik bintang
  • jerat

Saat Anda memodelkan jaringan menggunakan grafik, Anda dapat menggunakan semua kekuatan teori grafik untuk menganalisis jaringan.

Ini hanya satu untuk banyak aplikasi teori grafik dalam ilmu komputer.

gprime
sumber
-2

Struktur direktori adalah struktur pohon (dengan simpul akar dan simpul anak. Dalam jaringan itu digunakan untuk menemukan rute terpendek menggunakan pohon rentang minimum, algoritma Dijkstra.

Geetanjali
sumber