Граф-схема алгоритму

Граф-схема алгоритму (ГСА) — кінцевий зв'язний орієнтований граф ${\displaystyle G=\left\langle A,V\right\rangle }$, вершини якого ${\displaystyle a_{i}\in A,i={\overline {1,N}}}$ відповідають операторам, а дуги ${\displaystyle v_{k}=\left(a_{i},a_{j}\right)\in V,k={\overline {1,M}},i,j={\overline {1,N}}}$ задають порядок проходження вершин (операторів) алгоритму, де ${\displaystyle N=\ left|A\ right|}$ - число вершин графу, ${\displaystyle M=\left|V\right|}$ - число дуг. У ширшому сенсі вершинам графу відповідають не тільки операторні вершини, а й умовні, початкова та кінцева вершини і т.д. При розгляді паралельних алгоритмів вводиться поняття 'паралельної граф-схеми алгоритму' (ПарГСА), до складу якої входять вершини розпаралелювання / синхронізації, функціональність яких зазвичай поєднується. Іноді [1][2][3] до складу ГСА вводяться вершини додаткових типів: об'єднання альтернативних дуг (парна вершина для умовної вершини), фіктивні операторні вершини, вершини маркування (з метою забезпечення можливості моделювання виконання алгоритму мережею Петрі), очікувальні вершини.

Однак не будь-який орієнтований граф, складений з вершин зазначених вище типів, може бути ототожнений з коректним алгоритмом. Наприклад, з операторної вершини не може виходити більше однієї дуги. Тому на практиці зазвичай обмежуються розглядом підкласу граф-схем алгоритмів, що задовольняють умовам безпеки, живучості і стійкості[4] Алгоритми перетворення ГСА, які є підмножиною алгоритмів обробки графів загального вигляду, часто мають суттєві відмінності через використання особливих властивостей ГСА, що дозволяє їх спрощення, зниження часової або об'ємної складності[1][3][5].

До складу граф-схеми алгоритму можуть бути виділені більші елементи, представлені підмножинами її вершини і дуг: гілки (лінійні ланцюжки або ділянки вершин) і фрагменти (початковий, паралельний, альтернативний, циклічні з перед-, постумовою і перериванням). Еквівалентним записом граф-схеми коректного алгоритму є дерево фрагментів, що відбиває порядок вкладеності фрагментів.