4624
правки
Управляющий граф: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Управляющий граф''' ([[Control flow graph]], [[Flow graph]]) --- | '''Управляющий граф''' ([[Control flow graph]], [[Flow graph]]) --- | ||
основная модель программы, представляющая в виде орграфа | основная модель программы, представляющая в виде [[орграф|орграфа]] | ||
поток управления (систему управляющих связей) в программе; | поток управления (систему управляющих связей) в программе; | ||
в ней сохраняется только членение программы на операторы | в ней сохраняется только членение программы на операторы | ||
| Строка 7: | Строка 7: | ||
В общем случае '''управляющий граф''' --- это помеченный упорядоченный | В общем случае '''управляющий граф''' --- это помеченный упорядоченный | ||
мультиграф с выделенными ''начальной вершиной'' (''входом'') и непустым множеством ''конечных вершин'' (''выходов''). | [[мультиграф]] с выделенными ''[[начальная вершина|начальной вершиной]]'' (''[[вход|входом]]'') и непустым множеством ''[[конечная вершина|конечных вершин]]'' (''[[выход|выходов]]''). | ||
Обычно считается, что '''управляющий граф''' является [[Правильный уграф|''правильным'']] | Обычно считается, что '''управляющий граф''' является [[Правильный уграф|''правильным'']] | ||
и не содержит кратных дуг, вершин с совпадающими пометками и разных конечных вершин, т.е. | и не содержит [[кратные дуги|кратных дуг]], [[вершина|вершин]] с совпадающими пометками и разных конечных вершин, т.е. | ||
'''управляющий граф''' --- это орграф с | '''управляющий граф''' --- это орграф с | ||
выделенными ''начальной'' <math>s</math> и ''конечной'' <math>t</math> вершинами, | выделенными ''начальной'' <math>s</math> и ''конечной'' <math>t</math> вершинами, | ||
| Строка 17: | Строка 17: | ||
Часто без ограничения общности можно считать, что | Часто без ограничения общности можно считать, что | ||
из <math>t</math> не выходит и в <math>s</math> не заходит ни одна дуга '''управляющего графа''', а | из <math>t</math> не выходит и в <math>s</math> не заходит ни одна [[дуга]] '''управляющего графа''', а | ||
из каждой вершины, отличной от <math>t</math>, выходит одна или две дуги. | из каждой вершины, отличной от <math>t</math>, выходит одна или две дуги. | ||
