Начальный символ
порождающая грамматика
Сильносвязный граф
Предмет
Высшая математика
👍 Проверено
Автор24
ориентированный граф, для любых двух различных вершин a и b которого найдутся как путь из a в b, так и путь из b в a; ориентированный граф, для любых двух различных вершин a и b которого найдется или путь из a в b, или путь из b в a
Научные статьи на тему «Сильносвязный граф»
Свойства путей в графах и мультиграфах
Для n-вершинного сильносвязного орграфа оценена длина кратчайшего полного пути и, при наличии петли в графе, экспонент матрицы смежности вершин. Получена полиномиальная оценка субэкспонента системы матриц смежности вершин n-вершинных графов Гй,..., Гс, объединение которых сильно связно. Полученные результаты могут использоваться для исследования существенных переменных координатных функций, определяющих композиции преобразований множества конечных слов.
Creative Commons
Научный журнал
О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат
Сильносвязный орграф называется допустимым, если исходящие степени всех вершин в нём одинаковы и длины циклов взаимно просты в совокупности. Раскраской допустимого графа G назовем произвольный автомат A, граф которого совпадает с G. Слово называется синхронизирующим автомат A, если оно переводит его в одно и то же состояние вне зависимости от исходного состояния автомата A. Оптимальная раскраска допустимого графа -это раскраска с кратчайшим синхронизирующим словом среди всех синхронизирующих раскрасок. Длину соответствующего синхронизирующего слова назовем значением оптимальной раскраски. Доказано, что любой приближенный полиномиальный алгоритм для вычисления оптимальной раскраски или ее значения имеет относительную погрешность не меньше 2 в случае трехбуквенного алфавита при предположении P = NP. Также показано, как результат можно перенести на случай двухбуквенного алфавита.
Creative Commons
Научный журнал
Еще термины по предмету «Высшая математика»
- Графа
- Графит
- Графы
- Граф
- Шаровидный графит, сфероидальный графит
- Ориентированный граф (направленный граф)
- Плоский граф (планарный граф)
- Подграф графа
- Простой граф
- Теория графов
- Графа «Примечание»
- Графа «Размер»
- Графа «Сохранность»
- Белый графит
- Вторичный графит
- Третичный графит
- Чешуйчатый графит
- Эвтектический графит
- Эвтектоидный графит
- Вермикулярный графит
Повышай знания с онлайн-тренажером от Автор24!
- Напиши термин
- Выбери определение из предложенных или загрузи свое
- Тренажер от Автор24 поможет тебе выучить термины с помощью удобных и приятных карточек
