Отображение - граф
Cтраница 1
Отображения графов в графы и другие системы играют важную роль как в самой дискретной математике, так и в ее многочисленных приложениях, в том числе и, как можем в дальнейшем убедиться, в логическом управлении информационными процессами. [1]
Другая группа отображений графов связана с отношением порядка. Граф, изображенный на рис. 1.7, не является графом сравнимости. На рис. 1.11 изображен порядок, соответствующий графу, изображенному на рис. 1.12. Этот порядок представлен ориентированным графом. Такое представление избыточно в том смысле, что отношение порядка можно восстановить по графу, в котором нет дуг, соответствующих транзитивному замыканию. [2]
Аналогично для отображений графов Я и К. [3]
Относительно поставленной задачи отображения графов алгоритмов на архитектуры многопроцессорных ВС известно, что она является NP-сложной. По этой причине для ее решения малопригодны точные ( переборные) методы, типа метода ветвей и границ. [4]
В настоящем пункте описываются результаты численного исследования отображения графов алгоритмов линейной алгебры на полносвязные однородные графы ВС в зависимости от числа транспьютеров и скорости работы каналов мультитранспьютерной ВС. [5]
Этап обработки состоит в установлении взаимосвязи текущего предложения с остальным текстом, отображении графа текста на базу знаний ТСЦ, устранении возникающих несоответствий и в собственно обработке. Отображение осуществляется этапом интерпретации ( см. § 6.4) и заключается в поиске в знаниях ТСЦ фрагментов, наиболее близко соответствующих графу текста. Необходимо отметить, что в общем случае точное сопоставление не имеет места. Задача устранения несоответствий состоит в том, чтобы привести ( если это возможно) формат графа текста к формату знаний ТСЦ. Примером устранимого несоответствия является несоответствие, возникающее при обработке запроса об объеме выпуска некоторой продукции в I квартале 1978 года, если ТСЦ имеет сведения о ежемесячном выпуске этой продукции за 1978 год. Примером неустранимого несоответствия будет случай, когда входное предложение содержит запрос о выпуске продукции в январе, а ТСЦ имеет информацию только но кварталам. [6]
Так как к модулю добавляются вершины без связей, то преобразование д из условий утверждения, задающее отображение графа Gv на подрешетку, сохраняет соотношение смежности вершин. [7]
 |
Функция распределения / относительной ошибки 8 алгоритма A3 при разрезании графа сдваивания с п 15 на 1 - р - р 8 подграфов. [8] |
Хотя метод A3 и дает вполне удовлетворительные решения задачи распараллеливания для относительно небольших значений п р, его применение для отображения графов алгоритмов большой размерности на большое число процессоров проблематично в силу значительного возрастания времени работы метода и ухудшения точности получаемых решений. [9]
Хотя метод A3 и дает вполне удовлетворительные решения задачи распараллеливания для относительно небольших значений п, р, его применение для отображения графов алгоритмов большой размерности на большое число процессоров проблематично, в силу значительного возрастания времени работы метода и ухудшения точности получаемых решений. [10]
Если R ftr ll, r j e 0, 1 - атрица смежности графа G, то матрица смежности R г дополнения по отображению графа G до графа GX образуется из матрицы R путем замены всех единичных элементов на нулевые и всех нулевых на единичные. [11]
В заключение отметим, что, по крайней мере для тех отображений, которые приведены в этом параграфе, все эти отображения можно рассматривать как отображения графов в графы. [12]
Теорема 4.10. Для того чтобы граф G ( Z, S) разлагался в композицию двух графов, необходимо и достаточно существование подстановки t e Т множества Z, которая преобразует матрицу смежности R графа G ( дополнение по отображению графа G до насыщенного Gz) в правильную клеточную матрицу. [13]
Аналогично для отображений графов. [14]
 |
Зависимость ускорения S от числа процессоров / для различных алгоритмов линейной алгебры. [15] |
Страницы: 1 2