Šta je usmeren graf i koje su njegove osnovne karakteristike?

Usmereni graf (ili digraf) je struktura podataka koja se sastoji od skupa vrhova (čvorova) i skupa usmerenih ivica (lukova) koji povezuju te vrhove. Svaka ivica ima pravac koji pokazuje koji vrh je početni, a koji završni.

Glavne karakteristike:

• Vrhovi (Nodes / Vertices): Elementi grafa predstavljeni tačkama. Mogu označavati objekte, stanja ili faze.
• Ivice (Edges / Arcs): Veze između vrhova. U usmerenom grafu, ivica ima pravac koji ukazuje na prelaz sa jednog vrha na drugi. Predstavljaju se kao uređen par (u, v), gde je u početni vrh, a v završni.
• Pravac: Ključna osobina koja razlikuje usmeren graf od neusmerenog. Kretanje je moguće samo duž pravca ivice. Ivica od A do B ne znači da se može kretati od B do A, osim ako postoji posebna ivica od B do A.
• Petlje (Loops): Ivice koje povezuju vrh sa samim sobom (v, v).
• Višestruke ivice (Multiple Edges): Više ivica koje povezuju isti par vrhova u istom pravcu. U jednostavnim usmerenim grafovima, višestruke ivice nisu dozvoljene.
• Izolovani vrhovi: Vrhovi bez ulaznih i izlaznih ivica.
• Stepen vrha:
  • Ulazni stepen (In-degree): Broj ivica koje ulaze u vrh.
  • Izlazni stepen (Out-degree): Broj ivica koje izlaze iz vrha.

Primene u QA:

• Grafovi stanja za testiranje konačnih automata.
• Grafovi toka kontrole za analizu koda i kreiranje test slučajeva.
• Modelovanje zavisnosti u sistemima (npr. zavisnosti između servisa ili modula).
• Testiranje scenarija korišćenja sa strogim sekvencama akcija.