Apakah ada aljabar 'grafis' yang dapat menggambarkan 'bentuk' grafik?

Salah satu masalah utama dalam penghitungan grafik adalah menentukan 'bentuk' grafik, misalnya kelas isomorfisme dari grafik tertentu. Saya menyadari sepenuhnya bahwa setiap grafik dapat direpresentasikan sebagai matriks simetris. Namun, untuk mendapatkan bentuknya, Anda memerlukan kumpulan permutasi baris / kolom, yang membuat matriks sedikit kurang cocok. Ini juga agak sulit untuk 'melihat' grafik, setelah itu dalam bentuk itu.

Pertanyaan saya adalah: Apakah ada aljabar 'grafis' yang dapat menggambarkan 'bentuk' grafik?

Yang saya pikirkan adalah sistem formal macam apa yang cenderung muncul oleh para ahli topologi aljabar. Khususnya, hal-hal seperti aljabar untuk invarian simpul, atau sistem notasi seperti operad atau poligraf . 'Aljabar doodle' semacam ini hampir tidak berkembang dengan baik, jadi mungkin ada alasan untuk percaya bahwa tidak ada aljabar seperti itu untuk grafik, tapi saya pikir saya akan bertanya sebelum mengasumsikan sebaliknya.

MEMPERBARUI:

Pertanyaan saya mungkin sangat sempit dan tidak dapat langsung dijawab dengan 'ya', jadi jika moderator tidak keberatan, saya akan memperluasnya dengan bertanya:

Apakah ada sistem yang ada (jenis yang saya jelaskan di atas) yang dapat diadaptasi (dengan mudah atau tidak) untuk membuat sistem seperti itu? Jika ada lebih dari satu, jangan ragu untuk menyebutkan semuanya. Dan melempar yang sudah disebutkan juga.

Motivasi

Motivasi saya untuk pertanyaan seperti itu sebenarnya tentang mengklasifikasikan grafik asimetris. Saya hanya sarjana, jadi ulasan saya tentang keadaan saat ini dari teori grafik aljabar cukup tipis. Tapi saya belum melihat banyak, jika ada, bekerja dalam mencoba untuk menggambarkan secara sistematis semua grafik dengan cara aljabar, dan khususnya, yang menggunakan metafora visual daripada yang simbolik.

Contoh praktis di mana sistem seperti itu akan berguna

Misalkan seseorang ingin menggambarkan bukti bahwa semua grafik Euler harus memiliki simpul dengan derajat genap. Bukti standar biasanya menggunakan argumen tentang derajat genap dan ganjil, tanpa menyebutkan tepi sebenarnya yang digunakan. Seorang siswa biasa akan menemukan bukti seperti itu untuk pertama kalinya, dan mungkin mulai menggambar grafik, berusaha meyakinkan dirinya sendiri tentang argumen tersebut. Tetapi mungkin alat yang lebih baik daripada argumen 'logis' murni, adalah untuk menunjukkan bahwa kumpulan 'simbol' dari bahasa seperti itu tidak dapat memenuhi beberapa kondisi 'kelengkapan'.

Ya, saya tahu, saya menjadi tangan-bergelombang pada bagian terakhir ini .. Jika tidak, saya mungkin akan mulai membuat sistem seperti itu sendiri!

Tetapi mengabaikan ketidakjelasan saya sejenak, saya merasa bahwa banyak dari teorema lama dan terkenal dalam teori grafik tidak sulit tetapi memerlukan beberapa konseptualisasi bahwa kerangka kerja yang benar-benar baik dapat 'mengikat' dan 'mengemas' ke dalam pandangan yang seragam.

Banyak orang mencoba menemukan bahasa aljabar untuk menggambarkan bentuk grafik. Pertanyaan ini pada dasarnya adalah salah satu yang memotivasi teori grafik struktural .

Di jantung bidang matematika diskrit ini adalah studi tentang dekomposisi grafik. Beberapa orang yang bekerja di bidang ini adalah Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković, dan kolaborator mereka, meskipun daftar ini bias oleh minat penelitian saya sendiri.

Jenis penguraian grafik tertentu telah menghasilkan beberapa hasil paling umum dalam teori grafik. Misalnya, salah satu alat teknis utama yang dikembangkan untuk proyek grafik anak di bawah umur, yang mengarah pada teorema Robertson-Seymour , adalah teorema struktur grafik . Ini menunjukkan bahwa kelas grafik yang mengecualikan beberapa minor dapat dibangun dari grafik yang lebih sederhana.

$G$$G$$G, \overline{G}$$G$

Dekomposisi yang dipelajari sampai saat ini dalam beberapa hal non-aljabar. Intuisi pribadi saya adalah bahwa ada indikasi bahwa tidak ada sistem "baik" seperti yang Anda cari. Membuat pernyataan glib ini tepat kemungkinan akan membutuhkan perusahaan nontrivial dalam teori model hingga, tetapi saya menduga itu juga dapat mengarah pada hasil baru yang menarik dalam teori grafik (apakah berhasil atau tidak).

Pertanyaan ini penting dalam pemrograman fungsional karena representasi grafik pada umumnya tidak bagus dan tidak efisien untuk digunakan dalam bahasa yang murni fungsional.

Pendekatan yang bagus disajikan di ICFP tahun lalu: "Grafik Aljabar dengan Kelas (Mutiara Fungsional)" , oleh Andrey Mokhov.

Saya tidak tahu apakah itu sepenuhnya menjawab kebutuhan Anda, tetapi dapat mewakili secara aljabar berbagai jenis grafik terarah dan tidak terarah.