Analizorul grafic este un mediu vizual pentru lucrul cu grafice. Analizorul grafic nu oferă doar capacitatea de a crea și procesa grafice, dar vizualizează vizual rezultatele rezultate din algoritmii de lucru. Mediul acceptă lucrul cu grafice orientate și simple, încărcate și descărcate. Programul implementează mai mulți algoritmi pentru procesarea graficelor. începând de la căutarea căii și terminând cu verificarea pentru planaritate. Graphoanalyzer este un asistent de neînlocuit pentru rezolvarea problemelor cu ajutorul graficelor.
Vizualizarea graficelor și algoritmilor.
Procesul de creare și schimbare a unui grafic este intuitiv. Reprezentarea grafică a graficului este o formă de prezentare grafică foarte ușor de înțeles. De asemenea, puteți vedea rezultatul algoritmului în formă vizuală. O reprezentare vizuală poate fi salvată într-un fișier imagine. Pentru o mai mare claritate, puteți adăuga legende elementelor grafice, puteți schimba fundalul, personaliza aspectul elementelor grafice.
Interfața programului
Principala formă a programului este prezentată mai jos:
1 - meniul principal al programului;
2 - zona de lucru;
3 - fereastra matricei de adjuvant;
4 - câmpul de ieșire al rezultatului lucrării;
5 - butoane de comenzi rapide.
Figura 3.1 - Fereastra principală a aplicației
Dialogurile rămase sunt descrise în secțiunile corespunzătoare.
Alte funcții
Sarcinile tipice
Analizorul graficului 1.2 poate fi utilizat pentru a rezolva multe probleme care pot fi reduse la un model matematic al graficelor. Mai jos este o listă de sarcini tipice:
Un exemplu de rezolvare a problemelor: găsirea căii minime, găsirea costurilor minime pentru angajarea angajaților, găsirea costurilor minime pentru instalarea cablurilor sau a unei rețele de calculatoare.
Soluția pentru toate problemele constă în găsirea rutei minime în graficul încărcat.
Găsirea modului minim de călătorie
Trebuie să mergem de la casă la magazin, iar calea ar trebui să fie minimă. Să presupunem că avem o hartă stradală.
Figura 3.2 - Harta orașului
În primul rând, încărcați harta străzii ca fundal pentru zona de lucru.
Figura 3.3 - Fundal încărcat
Apoi setați scara (câți metri în 10 pixeli ai hărții)
Figura 3.4 - Setarea scalei
Apoi, tragem graficul pe baza hărții.
Figura 3.5 - graficul bazat pe grafic
Și acum găsim cea mai scurtă cale. folosind una dintre metodele (Ford-Bellman, Dijkstra sau Floyd). După căutarea celei mai scurte căi, vom vedea cea mai bună cale.
Figura 3.6 - Graficul cu minimul găsit
După cum vedem, calea cea mai scurtă este 460.
Găsirea costurilor minime pentru instalarea cablurilor sau a unei rețele de calculatoare
Problema este rezolvată în mod similar cu cea considerată mai sus, doar este necesar să se utilizeze o hartă a tuturor metodelor posibile de instalare a rețelei.
Căutați costuri minime pentru angajarea angajaților
Sarcina angajării angajaților este redusă la minimizarea căii.
De la 8 la 10 - 200 de ruble.
De la 14 la 18 - 500 de ruble
De la 19 la 20 - 50 de ruble
După cum puteți vedea din diagramă, există mai multe alternative, deși numărul lor nu este mare, dar acesta este doar un exemplu, în viața reală totul poate fi mai complicat.
Acum, pe baza acestor date, construim un grafic. Vârfurile graficului vor fi timestamps până la fiecare oră și arce, opțiuni de plată pentru angajați diferiți.
Figura 3.7 - Grafic pe baza programului de lucru
Acum, găsind calea cea mai scurtă de la primul vârf la cel precedent, definim costurile minime și metoda de angajare.
Figura 3.8 - Traseul minim găsit
Ca urmare, soluția corectă este următoarea, subliniată în verde:
Un exemplu de rezolvare a problemelor: distribuirea muncii între mai mulți angajați; Calculul debitului calculatorului sau al rețelei rutiere
Soluția ambelor probleme este redusă la găsirea debitului maxim. Numai problema distribuirii muncii între mai mulți angajați trebuie să fie redusă la ea.
Calculul debitului calculatorului sau al rețelei rutiere
Să presupunem că avem o secțiune din rețeaua rutieră prezentată în figura de mai jos.
Figura 3.9 - Foaia de parcurs
Trebuie să calculam debitul setului și drumurile într-o singură direcție. De exemplu, de la stânga la dreapta. Construim un grafic orientat și setăm greutățile arcilor egale cu lățimea de bandă. Toate drumurile din stânga și dreapta se conectează cu sursa și se scurge. Ca rezultat, obținem graficul:
Figura 3.10 - Grafic pe drumuri
Rămâne doar să se calculeze capacitatea de producție. Ca rezultat, obținem o astfel de distribuție a fluxului.
Figura 3.11 - Progresul maxim al drumurilor
Distribuirea muncii în rândul mai multor angajați
Distribuția muncii în rândul angajaților se reduce și la căutarea lățimii de bandă. Să avem o listă de angajați:
După cum se poate observa, diferite tipuri de muncă pot fi îndeplinite de angajați diferiți, iar condiția ca un loc de muncă să poată fi executat de un singur angajat.
Trebuie să distribuim lucrătorilor astfel încât să se efectueze numărul maxim de locuri de muncă. Pentru a face acest lucru manual este o sarcină consumatoare de timp dacă numărul de angajați este mare.
Pentru soluție, reprezentăm problema noastră sub forma unui grafic. Coloana din stânga a vârfurilor grafului este muncitorii, dreptul este tipul de lucru. De asemenea, am adăugat o chiuvetă și o sursă.
Acum vom conecta fiecare angajat cu tipul de muncă pe care îl poate îndeplini. Greutatea arcului a este egală cu 1.
Figura 3.12 - Graficul bazat pe angajați și tipurile de muncă
După ce conectăm sursa cu toți angajații și conectăm stocul cu tipurile de muncă. Greutatea este, de asemenea, egală cu 1.
Figura 3.13 - Grafic pe baza angajaților și a tipurilor de muncă
Acum căutăm bandă largă.
Figura 3.14 - Modul de distribuire a angajaților
Transmiterea ne-a arătat care angajat ar trebui să facă ce fel de muncă. De exemplu, Petrov ar trebui să cheltuiască bani, unchiul Petru trebuie să săpare.
Un exemplu de rezolvare a problemelor: găsirea celei mai ieftine opțiuni pentru instalarea cablurilor. Căutați cea mai ieftină cale de a conecta drumurile.
În timpul construcției de drumuri sau atunci când cablurile ouatului poate fi de mai multe moduri de compus oraș sau un calculator, dar este necesar să se facă o anumită metri fel. Mai mult decât atât, este de dorit ca metoda aleasă a fost cea mai economică în termeni de timp sau cheltuieli.
Să avem câteva orașe și modalități posibile de a le conecta.
Trebuie să conectăm toate orașele și să cheltuim cu privire la acest lucru și la cea mai mică sumă de bani. Transformați harta noastră într-un grafic.
Figura 3.15 - Harta orașelor
Figura 3.16 - Costul minim al construcției drumurilor
Ca rezultat, vom cheltui doar 73 de unități convenționale.
Exemplu de rezolvare a problemelor: Verificarea posibilității conectării componentelor electronice pe placă
La conectarea elementelor de pe placa electronică este necesar ca conexiunile să nu se suprapună. Pentru aceasta, lanțul eclectic trebuie reprezentat sub forma unui grafic. Dacă graficul este plan, atunci este posibil să conectați toate elementele lanțului fără intersecții.
Un exemplu de rezolvare a problemelor: găsirea unei metode de colorare a unei hărți cu un număr minim de culori
Dacă există o hartă pe care sunt situate țările și este necesar să se găsească o astfel de metodă de dezvăluire, astfel încât două linii învecinate să aibă culori diferite.
Să presupunem că există o hartă:
Figura 3.17 - Harta țării
Pentru a reprezenta o hartă ca un grafic, țările vor fi vârful graficului și limitele dungilor. Apoi graficul va arata astfel:
Figura 3.18 - Grafic pe țară
După ce căutăm numărul cromatic al graficului. și obținem următorul rezultat:
Figura 3.19 - Metoda de colorare a graficului
Exemplu de rezolvare a problemelor: Rezolvarea problemei vânzătorului călător
Să presupunem că o firmă sau un curier sau un vânzător care călătoresc are clienți și este necesar să vizitați toți clienții o singură dată.
Imaginați-vă clienții noștri sub forma unui grafic.
Figura 3.20 - Harta locației clientului
Pentru a găsi calea necesară, alegeți algoritmul de căutare pentru lanțul Hamiltonian.
Figura 3.21 - Traseul bypass-ului clientului
Prima operație pe care trebuie să o efectuați este să specificați graficul cu care veți lucra. Despre principalele etape ale sarcinii graficului:
Crearea unui grafic
Pentru a crea un grafic, trebuie mai întâi să selectați tipul acestuia. Figura 4.1 prezintă forma creării graficului.
Figura 4.1 - Forma de creare a graficului
Dacă bifați caseta "Orgraf", graficul va fi orientat. Dacă bifați caseta de selectare "Încărcat grafic", graficul va fi încărcat.
Pentru a crea un grafic, trebuie să apelați meniul "Creare".
Figura 4.2 - Meniul programului "Count"
Salvarea graficului
Pentru a salva graficul în scopul utilizării acestuia, este necesar să selectați elementul de meniu "File" - "Save graph".
Figura 4.3 - Imaginea meniului "Fișier"
Ca urmare, fișierul va fi salvat tipul graficului, poziția vârf, poziția și importanța inscripțiile. De asemenea, în meniu sunt salvate următoarele fișiere ale graficului cu care ați lucrat.
Păstrarea unei prezentări vizuale
Pentru a salva reprezentarea vizuală a graficului, este necesar să selectați elementul de meniu "Graph" - "Save Image". Ca rezultat, fișierul va fi salvat, ceea ce conduceți în spațiul de lucru.
Încărcarea unui grafic
Pentru a relua lucrul cu graficul salvat anterior, trebuie să încărcați graficul utilizând meniul Fișier - Load Graph.
Figura 4.4 - Imagine a meniului "Fișier"
Toate datele despre graficul folosit anterior vor fi pierdute.
Adăugarea unui vârf
Adăugarea unui vârf poate fi făcută în mai multe moduri:
Și folosiți tasta rapidă "F3".
Butonul de pe panou.
Și utilizați elementul din meniul Grafic.
Merită menționat faptul că vârful va fi adăugat la poziția aleatoare a spațiului de lucru. Dacă, sub forma unei numerotări de noduri, se selectează numerotarea aleasă de utilizator, va fi de asemenea necesar să introduceți numele vertexului.
Adăugarea unui arc
Adăugarea unui arc se poate face în mai multe moduri:
Și utilizați elementul de meniu din meniul "Count". După aceea, este necesar să introduceți numărul vârfului din care va merge arcul și în care. De asemenea, puteți utiliza tasta rapidă "F4".
În
Editați matricea de adjuvantă introducând o valoare în celula corespunzătoare.
Adăugarea de text
Puteți adăuga text pentru a crea text explicativ. Pentru a adăuga text, selectați elementul corespunzător din meniul "Graph" sau faceți clic pe butonul de pe bara de comenzi rapide. După aceasta, trebuie să alegeți un loc pentru locația inscripției și apoi să introduceți textul inscripției.
Ștergeți un obiect
Pentru a șterge obiecte (grafuri, arc sau vârfuri de înscriere), selectați-le făcând clic pe ele cu butonul drept al mouse-ului și selectați un element din meniul "Graph" sau faceți clic pe butonul de pe panou.
Obiecte Moving
Pentru a muta obiecte (vârfuri ale unui grafic, arce sau inscripții), faceți clic pe obiectul butonului stâng al mouse-ului și, fără a îl elibera, efectuați mișcarea mouse-ului.
Redenumirea obiectelor
Pentru a redenumi nodurile, a schimba greutatea arcurilor și a redenumi etichetele, trebuie să selectați elementul de interes. Accesați meniul Editare și selectați unul dintre elementele:
- Pentru a edita numele vertexului, în modul de nume dat de utilizator.
- pentru editarea greutății arcurilor, pentru grafice încărcate.
- pentru a schimba textul etichetei.
Editarea matricei de adjudecare
Editarea matricei de adjunct poate fi efectuată în 2 moduri diferite.
Prima metodă este să utilizați panoul matricii de adjudecare pentru a edita greutățile arcurilor.
Figura 4.5 - Fereastra de editare a matricei adiacente
Când se editează neorograful, se va adăuga automat a doua valoare. Dacă introduceți valori incorecte, va fi afișat un mesaj.
În
Moduri de manipulare a mouse-ului
Modul de procesare a mouse-ului determină prelucrarea clicului din dreapta al mouse-ului. Există 2 moduri de procesare a mouse-ului: