Universal graph
http://dbpedia.org/resource/Universal_graph an entity of type: Software
En mathématiques et en informatique théorique, un graphe universel est un graphe infini qui contient tous les graphes finis (ou dénombrables) comme sous-graphes. Le premier graphe universel a été introduit par Richard Rado et s’appelle le graphe de Rado (encore appelé graphe aléatoire). C'est l'analogue des nombres univers qui contiennent dans leurs décimales toutes les suites finies de chiffres.
rdf:langString
En teoría de grafos, un grafo universal es un grafo infinito que contiene a todos los grafos finitos (o al menos numerables) como un subgrafo inducido. El primer grafo universal fue construido por R. Rado, actualmente llamado o grafo aleatorio. En terminología matemática más antigua, la frase "grafo universal" fue a veces utilizada para denotar a los grafos completos.
rdf:langString
In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent workhas focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs. The notion of universal graph has been adapted and used for solving mean payoff games.
rdf:langString
Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик.
rdf:langString
Універса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо і цей граф тепер називають графом Радо або випадковим графом. Свіжіші роботи фокусуються на універсальних графах для сімейства графів F. Тобто нескінченний граф, що належить F, який містить усі скінченні графи сімейства F. Наприклад, графи Генсона є універсальними в цьому сенсі для графів без i-клік. У старій математичній термінології фразу «універсальний граф» іноді використовували для повного графа.
rdf:langString
rdf:langString
Grafo universal
rdf:langString
Graphe universel
rdf:langString
Универсальный граф
rdf:langString
Universal graph
rdf:langString
Універсальний граф
xsd:integer
1452141
xsd:integer
1112303554
rdf:langString
En teoría de grafos, un grafo universal es un grafo infinito que contiene a todos los grafos finitos (o al menos numerables) como un subgrafo inducido. El primer grafo universal fue construido por R. Rado, actualmente llamado o grafo aleatorio. Trabajos más recientes se han enfocado en grafos universales para una familia de grafos particular F, correspondiente a aquella que contiene a todos los grafos finitos. Un grafo universal para una familia F de grafos también puede referirse a un miembro de una secuencia de grafos finitos que contiene a todos los grafos en F. Por ejemplo, cada árbol finito es un subgrafo de un grafo hipercubo suficientemente largo; por lo tanto, un hipercubo puede decirse que es un grafo universal para los árboles. En terminología matemática más antigua, la frase "grafo universal" fue a veces utilizada para denotar a los grafos completos.
rdf:langString
En mathématiques et en informatique théorique, un graphe universel est un graphe infini qui contient tous les graphes finis (ou dénombrables) comme sous-graphes. Le premier graphe universel a été introduit par Richard Rado et s’appelle le graphe de Rado (encore appelé graphe aléatoire). C'est l'analogue des nombres univers qui contiennent dans leurs décimales toutes les suites finies de chiffres.
rdf:langString
In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent workhas focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs. A universal graph for a family F of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in F; for instance, every finite tree is a subgraph of a sufficiently large hypercube graphso a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for n-vertex trees, with only n vertices and O(n log n) edges, and that this is optimal. A construction based on the planar separator theorem can be used to show that n-vertex planar graphs have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs have universal graphs with O(n log n) edges. It is also possible to construct universal graphs for planar graphs that have n1+o(1) vertices. Sumner's conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2n − 2 vertices contains every polytree with n vertices as a subgraph. A family F of graphs has a universal graph of polynomial size, containing every n-vertex graph as an induced subgraph, if and only if it has an adjacency labelling scheme in which vertices may be labeled by O(log n)-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in F may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label. In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph. The notion of universal graph has been adapted and used for solving mean payoff games.
rdf:langString
Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик. Универсальный граф для семейства графов F может также пониматься как член последовательности конечных графов, которые содержат все графы из F. Например, любое конечное дерево является подграфом достаточно большого графа гиперкуба, так что можно сказать, что гиперкуб является универсальным графом для деревьев. Однако это не самый маленький такой граф — известно, что существует универсальный граф для деревьев с n вершинами, содержащий всего n вершин и O(n log n) рёбер, и этот граф оптимален. Построение, основанное на теореме о планарном разбиении, может быть использовано, чтобы показать, что планарные графы с n вершинами имеет универсальные графы с O(n3/2) рёбрами, и что планарные графы ограниченной степени имеют универсальные графы с O(n log n) рёбрами. Гипотеза Самнера утверждает, что турниры являются универсальными для в том смысле, что любой турнир с 2n − 2 вершинами содержат любое полидерево с n вершинами в качестве поддерева. Семейство графов F имеет универсальный граф полиномиальная размера, содержащий любой граф с n вершинами в качестве порождённого подграфа, тогда и только тогда, когда он имеет , в которой вершины могут быть помечены O(log n)-битными строками таким образом, что алгоритм может определить, смежны ли вершины, по меткам этих вершин. Если граф этого типа существует, вершины любого графа в F можно пометить метками соответствующих вершин универсального графа, и наоборот, если схема разметки существует, может быть построен универсальный граф, содержащий все возможные метки. В старой математической терминологии фраза "универсальный граф" иногда использовался для полного графа.
rdf:langString
Універса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо і цей граф тепер називають графом Радо або випадковим графом. Свіжіші роботи фокусуються на універсальних графах для сімейства графів F. Тобто нескінченний граф, що належить F, який містить усі скінченні графи сімейства F. Наприклад, графи Генсона є універсальними в цьому сенсі для графів без i-клік. Універсальний граф для сімейства графів F можна також розуміти як член послідовності скінченних графів, які містять усі графи з F. Наприклад, будь-яке скінченне дерево є підграфом достатньо великого графа гіперкуба, так що можна сказати, що гіперкуб є універсальним графом для дерев. Однак це не найменший такий граф — відомо, що існує універсальний граф для дерев з n вершинами, що містить всього n вершин і O(n log n) ребер, і цей граф оптимальний. Побудову, засновану на теоремі про планарне розбиття, можна використати, щоб показати, що планарні графи з n вершинами мають універсальні графи з O(n3/2) ребрами, і що планарні графи обмеженого степеня мають універсальні графи з O(n log n) ребрами. Гіпотеза Самнера стверджує, що турнір є універсальними для у тому сенсі, що будь-який турнір з 2n − 2 вершинами містить будь-яке полідерево з n вершинами як піддерево. Сімейство графів F має універсальний граф поліноміального розміру, що містить будь-який граф з n вершинами як породжений підграф, тоді й лише тоді, коли він має , в якій вершини можна позначити O(log n)-бітовими рядками так, що алгоритм може визначити, чи суміжні вершини, за мітками цих вершин. Якщо граф цього типу існує, вершини будь-якого графа в F можна позначити мітками відповідних вершин універсального графа, і навпаки, якщо схема розмітки існує, можна побудувати універсальний граф, що містить усі можливі мітки. У старій математичній термінології фразу «універсальний граф» іноді використовували для повного графа.
xsd:nonNegativeInteger
8657