40.Методы систематического обхода вершин графа. Поиск в глубину.

Поиск в глубину. Становимся в произвол. вершину графа, отмечаем её единицей. Из смежных с ней вершин выбираем произвольную, становимся в неё, отмечаем её 2 и т.д., пока возможно отмечать новые вершины. Если отмечать с новой вершины невозможно, а неотмеченные есть, то становимся в любую из неотмеченных и продолжаем отмечать.

41. Методы систематического обхода вершин графа. Поиск в ширину.

Поиск в ширину. Становимся в произвол. вершину графа, отмечаем её. Просматриваем вершины, смежные с ней и отмечаем их все. Становимся в любую из только что отмеченных и отмечаем все смежные с ней, не имеющие меток. Далее становимся во вторую из отмеченных ранее и отмечаем все смежные с ней. Делаем, пока возможна разметка. Если остались неотмеченные и разметка невозможна, становимся в любую из отмеченных и т.д.

42. Схемы из функциональных элементов.Схема из функциональных элементов – математическая модель вычислителя булевой функции, представленной некоторой формулой, собранного из структурных элементов, каждый из которых вычисляет одну из «базисных» булевых функций. Математичеси «схема» определяется как ориентированный граф спец. вида, в котором и вершины и дуги снабжены некоторыми метками.