| dbo:abstract
|
- En teoría de grafos, un grafo umbral (mejor conocido en inglés como threshold graph) es un grafo que puede ser construido desde un único vértice aplicando repetidamente cualquiera de las siguientes dos operaciones: 1.
* Adición de un vértice aislado al grafo, es decir, de un vértice con grado 0. 2.
* Adición de un vértice dominante al grafo, es decir, de un vértice que está conectado a todos los demás vértices. Por ejemplo, el grafo de la figura es un grafo umbral. Puede construirse comenzando con el vértice 1, y luego añadiendo vértices negros como vértices aislados y vértices rojos como vértices dominantes, siguiendo el orden en que están enumerados. (es)
- En théorie des graphes, un graphe à seuil est un graphe qui peut être construit, en partant d'un graphe à un seul sommet, par application répétée d'une des deux opérations suivantes : 1.
* Ajout d'un sommet isolé au graphe. 2.
* Ajout d'un sommet dominant au graphe, c'est-à-dire d'un sommet connecté à tous les autres sommets. Par exemple, le graphe de la figure ci-contre est un graphe de seuil : il peut être construit en commençant par un graphe à un seul sommet (sommet 1), puis en ajoutant les sept autres dans l'ordre dans lequel ils sont numérotés, les sommets noirs comme sommets isolés et les sommets rouges comme sommets dominants. Les graphes à seuil ont été introduits par Chvátal et Hammer en 1977 . Un chapitre sur les graphes à seuil apparaît dans le livre de Golumbic de 1980, et le livre de Mahadev et Peled de 1995 leur est consacré. Comme le notent Diaconis, Holmes et Janson, parmi les 64 graphes étiquetés à 4 sommets, il y a 46 graphes à seuil ; les 18 autres sont des chaînes à 4 sommets (notés , des cycles à 4 sommets (notés ) et leurs compléments qui sont des paires d'arêtes (notés ). Si on considère les graphes non étiquetés, il y a 11 graphes à 4 sommets, dont 8 sont des graphes à seuil. (fr)
- In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: 1.
* Addition of a single isolated vertex to the graph. 2.
* Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices. For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered. Threshold graphs were first introduced by . A chapter on threshold graphs appears in , and the book is devoted to them. (en)
- В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций: 1.
* Добавление в граф одной изолированной вершины 2.
* Добавление одной доминирующей вершины в граф, т.е. отдельной вершины, связанной со всеми остальными вершинами. Например, граф на рисунке является пороговым графом. Он может быть построен с одной вершины (вершина 1), и добавления чёрных вершин как изолированных вершин и красных вершин как доминирующих вершин в порядке нумерации. Пороговые графы были введены Хваталом и Хаммером. Глава, посвящённая графам, появилась в книге Голумбика, а книга Махадева и Пеледа полностью посвящена пороговым графам. (ru)
- У теорії графів пороговий граф — це граф, який можна побудувати з одновершинного графу послідовним виконанням таких двох операцій: 1.
* Додавання в граф однієї ізольованої вершини 2.
* Додавання однієї домінівної вершини в граф, тобто окремої вершини, пов'язаної з усіма іншими вершинами. Наприклад, граф на малюнку є пороговим графом. Його можна побудувати з однієї вершини (вершина 1), додавши чорні вершини як ізольовані вершин і червоні вершини як домінівні вершини в порядку нумерації. Порогові графи ввели Хватал і Гаммер. Розділ, присвячений цим графам, з'явився в книзі Голумбіка, а книга Махадева і Пеледа повністю присвячена пороговим графам. (uk)
|
| rdfs:comment
|
- En teoría de grafos, un grafo umbral (mejor conocido en inglés como threshold graph) es un grafo que puede ser construido desde un único vértice aplicando repetidamente cualquiera de las siguientes dos operaciones: 1.
* Adición de un vértice aislado al grafo, es decir, de un vértice con grado 0. 2.
* Adición de un vértice dominante al grafo, es decir, de un vértice que está conectado a todos los demás vértices. (es)
- En théorie des graphes, un graphe à seuil est un graphe qui peut être construit, en partant d'un graphe à un seul sommet, par application répétée d'une des deux opérations suivantes : 1.
* Ajout d'un sommet isolé au graphe. 2.
* Ajout d'un sommet dominant au graphe, c'est-à-dire d'un sommet connecté à tous les autres sommets. Les graphes à seuil ont été introduits par Chvátal et Hammer en 1977 . Un chapitre sur les graphes à seuil apparaît dans le livre de Golumbic de 1980, et le livre de Mahadev et Peled de 1995 leur est consacré. (fr)
- In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: 1.
* Addition of a single isolated vertex to the graph. 2.
* Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices. For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered. (en)
- В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций: 1.
* Добавление в граф одной изолированной вершины 2.
* Добавление одной доминирующей вершины в граф, т.е. отдельной вершины, связанной со всеми остальными вершинами. Например, граф на рисунке является пороговым графом. Он может быть построен с одной вершины (вершина 1), и добавления чёрных вершин как изолированных вершин и красных вершин как доминирующих вершин в порядке нумерации. (ru)
- У теорії графів пороговий граф — це граф, який можна побудувати з одновершинного графу послідовним виконанням таких двох операцій: 1.
* Додавання в граф однієї ізольованої вершини 2.
* Додавання однієї домінівної вершини в граф, тобто окремої вершини, пов'язаної з усіма іншими вершинами. Наприклад, граф на малюнку є пороговим графом. Його можна побудувати з однієї вершини (вершина 1), додавши чорні вершини як ізольовані вершин і червоні вершини як домінівні вершини в порядку нумерації. (uk)
|
