Structurile grafice sunt utilizate în multe aplicații, cum ar fi reprezentarea relațiilor, situații sau probleme. Un grafic este definit ca un set de noduri și un set de muchii în care fiecare margine conectează o pereche de noduri. Dacă muchiile sunt orientate, ele sunt numite și arce. Arcurile sunt reprezentate cu ajutorul unor perechi ordonate de noduri. Un astfel de grafic este numit orientat. Riburile pot fi adaptate costurilor, denumirilor sau denumirilor de orice fel, în funcție de aplicație. Exemple de grafice sunt prezentate în figura 9.11.
Fig. 9.11. Exemple de grafice sunt: a) un grafic simplu; b) Graficul orientat cu valori atribuite arcurilor
Graficele pot fi reprezentate în limba Prolog în mai multe moduri. Una dintre metode este ca fiecare margine sau fiecare arc să fie reprezentată separat, sub forma unei singure propoziții. Prin urmare, graficele prezentate în Fig. 9.11, pot fi reprezentate folosind seturi de propoziții, de exemplu, după cum urmează:
conectat! a, b). conectat! B, c).
O altă metodă este aceea că întregul grafic poate fi reprezentat ca un obiect de date. Prin urmare, graficul este reprezentat ca o pereche de două seturi: noduri și muchii. Fiecare set de noduri poate fi reprezentat ca o listă și fiecare margine din setul de muchii este o pereche de noduri. Pentru a îmbina ambele seturi într-o pereche vom selecta functorul grafic, iar pentru reprezentarea margini vom folosi functorul e. Astfel, una din metodele de reprezentare a graficului (neorientat), arătat în Fig. 9.11, arată astfel: G1 = grafic; ta, b, c, dj. te (a, b>, e (b, dj, e (b, c), e; c, d;
Pentru a reprezenta un grafic direcționat, puteți alege functorii digraph și a (pentru arce). Prin urmare, graficul orientat prezentat în Fig. 9.11. are următoarea formă: G2 = digraph! [s, t, u, v], [a (s, t, 3>, af 2Jl>
Dacă fiecare nod este asociat cu cel puțin un alt nod, puteți dezactiva lista de noduri din această vizualizare, deoarece în acest caz setul de noduri este specificat implicit de lista de margini.
O altă metodă este aceea că fiecare nod este asociat cu o listă de noduri care sunt adiacente acestui nod. În acest caz, graficul este o listă
Partea I. Prolog limba
O pereche formată dintr-un nod și o listă corespunzătoare de contiguitate. Prin urmare, graficele considerate ca exemple pot fi reprezentate după cum urmează;
Desigur, simbolurile de mai sus "->" și "/" sunt operatori infix.
Alegerea celei mai potrivite reprezentări depinde de aplicație și de ce operații ar trebui efectuate cu graficele. Cele două operații cele mai comune sunt după cum urmează.
• Găsirea unei căi între două noduri specificate,
• O căutare în graficul unui subgraf care are unele date
proprietăți.
Un exemplu de operație de tip ultim este căutarea arborelui de acoperire al graficului. Următoarele secțiuni discută câteva programe simple pentru găsirea căii și formarea unui copac de spanning.