азивається його початковою вершиною, а - кінцевої. p> Циклічний маршрут в орграфе - це маршрут, у якому початкова та кінцева вершини збігаються.
Маршрут, в якому ніяка дуга не зустрічається більше одного разу, називається шляхом.
Шлях, кожна вершина якого належить не більш ніж двом його дуг, є простим.
Простий циклічний шлях називають контуром, а простий шлях, який не є контуром, - бесконтурним шляхом або (орієнтованої) ланцюгом.
Довжиною маршруту називається кількість складові його дуг.
Кажуть, що вершина досяжна з вершини, якщо в орграфе існує шлях ізв. Відстань від до - це довжина найкоротшого шляху з вершини у вершину. Ставлення досяжності позначають. p> Матриця
В
є матрицею відносини досяжності в орграфе, що має матрицю суміжності. Матриця називається матрицею досяжності орграфа. p> Симетрична частина ставлення досяжності називається відношенням взаємної досяжності. Класи відносини взаємної досяжності називають сильними компонентами (або шарами) орграфа. p> Орграф, за визначенням, є сильно зв'язковим, якщо відношення універсально на ньому, тобто якщо кожна його вершина досяжна з будь-якої іншої.
Нехай дано орграфов відношення еквівалентності на множині його вершин.
Факторграфом орграфа по еквівалентності називається орграф, вершинами якого є класи еквівалентності. При цьому з вершини проводиться дуга в, якщо існує вершина з класу і з класу, такі, що. p> Вершина орграфа, що не досяжна з інших його вершин, називається джерелом, а вершина, з якої не досяжна ніяка інша вершина - стоком.
Нехай орграф є функціональною моделлю деякої системи, що допускає одиночний відмову. Для виявлення відмови проводиться перевірка елементів системи, що має для кожного елемента два результати: 0, якщо реакція елемента допустима, 1 в іншому випадку. Припустимо, що система така, що реакція 1, відзначена у деякої елемента, успадковується всіма досяжними з нього (в сенсі орграфа) елементами. Під перевіряючим тестом розуміється деяка сукупність перевірок елементів системи, що дозволяє з'ясувати, чи є в системі відмову (без його локалізації). br/>
. Теорема
Перевіряючий тест для системи мінімальний тоді і тільки тоді, коли він складається з перевірок елементів, які відповідають вершинам орграфа, узятим по одній з кожного стоку факторграфа.
Доказ
Нехай тест не містить перевірки жодного представника стокафакторграфа. Тоді відмова будь-якого елемента, представленого вершиною, що входить в клас, що не розпізнається даними тестом, і, значить, тест не є перевіряючим. Таким чином, будь-який перевіряючий тест містить перевірки представників усіх стоків у. p> Нехай до складу перевіряючого тесту входить перевірка деякої вершини орграфа, що не входить ні в один стік факторграфа. У разі відмови відповідного елемента результатом перевірки буде 1. Але тоді значення 1 дає і перевірка будь-якого представника того стоку в, який досяжний з...
