Свойство - граф
Cтраница 1
Свойства графов, связанные с существованием в графе циклов, весьма существенны для многих прикладных задач, в том числе и рассматриваемых здесь. [1]
Свойство графов, которое легко реально доказать для каждого графа, имея этот граф, называют NP-свойством. Это высказывание можно просто истолковать следующим образом: число шагов в формальном доказательстве того, что граф обладает данным свойством, не должно превосходить некоторого полинома от числа вершин и ребер графа G. Такое толкование несколько расплывчато, но неким оправданием для него служит то обстоятельство, что класс определенных таким образом NP-свойств является достаточно естественным и оказался весьма полезным. [2]
Изучение свойств графа упрощается при использовании некоторых характеризующих его чисел, инвариант-ных относительно изоморфизма. [3]
 |
Маркированный граф. [4] |
Изучены такие свойства маркированных графов, как активность, безопасность и достижимость. Наиболее интересными структурными компонентами маркированного графа при изучении указанных свойств являются его циклы. [5]
Поэтому вопросы перспект ральных свойств графов де Брейна вызывают значительный интерес и требуют дальнейшего рассмотрения. [6]
 |
Матрицы инциденций для графов на. [7] |
Пусть Р - некоторое свойство графа ( P ( G) - Q или P ( G) 1 в зависимости от того, обладает или не обладает G нашим свойством. [8]
Третья проблема касается изучения свойств графов ( 1-скелетов) многогранников ( гл. Фундаментальными здесь являются теоремы Штейница и Балинского. Первая из них утверждает, что граф является 1-скелетом 3-мерного многогранника тогда и только тогда, когда он планарен и трехсвязен, вторая - что граф d - мерного многогранника является cf - связным. [9]
В первом направлении при изучении свойств графов используют общие свойства матриц и определителей. [10]
Мораль этой сказки такова: существуют свойства графов, наличие которых легко проверить, если они имеют место. Если у графа есть совершенное паросочетание или гамильтонов цикл, то это может быть легко доказано построением такового. Если двудольный граф не имеет совершенного паросочетания, то это можно доказать путем выделения в каком-либо цветном классе такого подмножества X, у которого меньше чем Х соседей в другом цветном классе. [11]
Большой класс вычислительных проблем включает определение свойств графов, ориентированных графов, целых чисел, массивов целых чисел, конечных семейств конечных множеств, булевых формул и элементов других счетных множеств. Посредством простого кодирования таких объектов множествами слов над конечным алфавитом эти проблемы могут быть превращены в проблемы распознавания языков и можно исследовать их вычислительную сложность. Имеет смысл считать, что такая проблема решается удовлетворительно, если найден алгоритм для ее решения, оканчивающий свою работу за время ( число шагов), ограниченное полиномом от длины входного слова. [12]
Моей ученице Е. Н. Ефимовой я благодарен за неоднократные обсуждения свойств графов, возникающих в лингвистике. [13]
Теорема 1 позволяет получить много интересных утверждений о свойствах графа автомата Arnd. [14]
Для накопления фактов, позволяющих выдвигать различные гипотезы о свойствах графов, очень полезно иметь диаграммы графов. Легко изобразить все графы, содержащие менее 6 вершин. Диаграммы графов с 6 вершинами, представленные здесь, были выполнены Кроуэм. [15]
Страницы: 1 2 3 4