Mis on suunatud graaf ja millised on selle peamised omadused?

Suuna graf (või diagraf) on andmestruktuur, mis koosneb tippudest (sõlmedest) ja suunatud servadest (liinidest), mis ühendavad neid tippe. Igal serval on suund, mis näitab, milline tipp on alguspunkt ja milline lõpp.

Peamised omadused:

• Tipud (Nodes / Vertices): Graafi elemendid, kujutatud punktidena. Võivad tähistada objekte, olekuid või etappe.
• Servad (Edges / Arcs): Seosed tippude vahel. Suunatud graafis on serval suund, mis näitab üleminekut ühest tipust teise. Märgitud järjestatud paarina (u, v), kus u on alguspunkt ja v lõpp.
• Suund: Peamine omadus, mis eristab suunatud graafi mittesuunatud graafist. Ülekanne on võimalik ainult serva suuna järgi. Serv A-st B-sse ei tähenda, et saaks liikuda B-st A-sse, kui pole eraldi serva B-st A-sse.
• Silmused (Loops): Serv, mis ühendab tippu iseendaga (v, v).
• Mitmekordsed servad (Multiple Edges): Mitmed servad, mis ühendavad sama tippude paari samas suunas. Lihtsas suunatud graafis ei lubata mitmekordseid servi.
• Isoleeritud tipud: Tippud, millel pole sisenevaid ega väljuvaid servi.
• Tipu aste:
  • Sisseastuva aste (In-degree): Kui palju servi sisenevad tippu.
  • Väljuva aste (Out-degree): Kui palju servi väljuvad tippu.

Rakendused QA-s:

• Oleku graafid lõplikute automaatide testimiseks.
• Juhtimisvoogude graafid koodi analüüsiks ja testjuhtumite koostamiseks.
• Sõltuvuste modelleerimine süsteemides (näiteks sõltuvused teenuste või moodulite vahel).
• Kasutusstsenaariumite testimine rangelt järjestatud tegevustega.