| dbo:abstract
|
- Eine graziöse Beschriftung eines Graphen mit Kanten ist eine Beschriftung der Knoten mit unterschiedlichen Zahlen zwischen 1 und , sodass dadurch jede Kante eine eindeutige Beschriftungen erhält. Die Beschriftung einer Kante ergibt sich als Differenz der Beschriftungen ihrer beiden Endknoten. Ein Graph, für den eine solche Beschriftung existiert, wird graziöser Graph genannt. Gibt es zusätzlich eine Zahl , sodass ein Knoten einer jeden Kante mit einer Zahl kleiner als und der andere mit einer Zahl größer oder gleich beschriftet ist, dann handelt es sich um eine bipartite Beschriftung. Die Bezeichnung graziöse Beschriftung geht zurück auf Solomon W. Golomb. Ursprünglich verwendete Alexander Rosa die Bezeichnung β-Bewertung in seinem 1967 veröffentlichten Aufsatz über Graphenbeschriftungen. Bipartite Beschriftungen nannte er α-Bewertungen. Eines der ungelösten Probleme der Mathematik ist die Graziöser-Baum-Vermutung, der zufolge es für alle Bäume eine graziöse Beschriftung gibt. (de)
- In graph theory, a graceful labeling of a graph with m edges is a labeling of its vertices with some subset of the integers from 0 to m inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and m inclusive. A graph which admits a graceful labeling is called a graceful graph. The name "graceful labeling" is due to Solomon W. Golomb; this type of labeling was originally given the name β-labeling by Alexander Rosa in a 1967 paper on graph labelings. A major conjecture in graph theory is the graceful tree conjecture or Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, and sometimes abbreviated GTC. It hypothesizes that all trees are graceful. It is still an open conjecture, although a related but weaker conjecture known as "Ringel's conjecture" was partially proven in 2020. Kotzig once called the effort to prove the conjecture a "disease". Another weaker version of graceful labelling is near-graceful labeling, in which the vertices can be labeled using some subset of the integers on [0, m + 1] such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints (this magnitude lies on [1, m + 1]). Another conjecture in graph theory is Rosa's Conjecture, named after Alexander Rosa, which says that all triangular cacti are graceful or nearly-graceful. A graceful graph with edges 0 to m is conjectured to have no fewer than vertices, due to sparse ruler results. This conjecture has been verified for all graphs with 213 or fewer edges. (en)
- En théorie des graphes, un étiquetage gracieux d'un graphe non orienté à m arêtes est un étiquetage de ses sommets par des entiers naturels distincts pris dans l'ensemble {0,...,m} qui a la propriété que les valeurs absolues des différences des étiquettes des extrémités des arêtes sont toutes distinctes et égales à 1,...,m ; elles identifient ainsi de manière unique les arêtes. Un graphe qui admet un étiquetage gracieux est un graphe gracieux. Le terme « étiquetage gracieux » (en anglais « graceful labeling ») apparaît dans un article de Solomon W. GolombLe concept figure, sous le nom de « β-labeling » dans un article d'Alexander Rosa sur l’étiquetage de graphes. (fr)
- Грациозная разметка в теории графов — такая вершинная разметка графа с рёбрами некоторым подмножеством целых чисел между 0 и включительно, что разные вершины помечены разными числами, и такая, что, если каждое ребро пометить абсолютной разностью меток вершин, которое оно соединяет, то все полученные разности будут различными. Граф, который допускает грациозную разметку, называется грациозным графом. Автором термина «грациозная разметка» является Соломон Голомб; (англ. Alexander Rosa) был первым, кто выделил этот класс разметок и ввёл его под названием -разметки в статье 1967 года про разметки графов.. Одной из главных недоказанных гипотез в теории графов является гипотеза грациозности деревьев (англ. Graceful Tree Conjecture), также известная как гипотеза Рингеля — Коцига по именам сформулировавших её Герхарда Рингеля и (англ. Anton Kotzig), которая утверждает, что все деревья грациозны. По состоянию на 2017 год гипотеза всё ещё не доказана, но из-за простоты формулировки привлекла широкое внимание (вследствие чего появилось много неправильных доказательств), Коциг в своё время даже охарактеризовал массовые попытки доказать её как «заболевание». (ru)
- Граціозна розмітка в теорії графів — така вершинна розмітка графу з ребрами деякою підмножиною цілих чисел між 0 і включно, що різні вершини позначено різними числами, і така, що, якщо кожне ребро позначити абсолютною різницею міток вершин, які воно з'єднує, то всі отримані різниці будуть різними. Граф, який допускає граціозну розмітку, називають граціозним графом. Автором терміна «граціозна розмітка» є Соломон Ґоломб; Александер Роса був першим, хто виділив цей клас розміток і ввів його під назвою -розмітка в статті про розмітки графів.. Однією з головних недоведених гіпотез у теорії графів є гіпотеза граціозності дерев (англ. Graceful Tree Conjecture), також відома як гіпотеза Рінгеля — Коціга за іменами її авторів і , яка стверджує, що всі дерева граціозні. Станом на 2017 гіпотезу все ще не доведено, але простота формулювання привернула широку увагу математиків-аматорів (внаслідок чого з'явилося багато неправильних доведень), Коціг свого часу навіть охарактеризував масові спроби довести її як «хворобу». (uk)
|
| rdfs:comment
|
- In graph theory, a graceful labeling of a graph with m edges is a labeling of its vertices with some subset of the integers from 0 to m inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and m inclusive. A graph which admits a graceful labeling is called a graceful graph. The name "graceful labeling" is due to Solomon W. Golomb; this type of labeling was originally given the name β-labeling by Alexander Rosa in a 1967 paper on graph labelings. (en)
- Eine graziöse Beschriftung eines Graphen mit Kanten ist eine Beschriftung der Knoten mit unterschiedlichen Zahlen zwischen 1 und , sodass dadurch jede Kante eine eindeutige Beschriftungen erhält. Die Beschriftung einer Kante ergibt sich als Differenz der Beschriftungen ihrer beiden Endknoten. Ein Graph, für den eine solche Beschriftung existiert, wird graziöser Graph genannt. Gibt es zusätzlich eine Zahl , sodass ein Knoten einer jeden Kante mit einer Zahl kleiner als und der andere mit einer Zahl größer oder gleich beschriftet ist, dann handelt es sich um eine bipartite Beschriftung. (de)
- En théorie des graphes, un étiquetage gracieux d'un graphe non orienté à m arêtes est un étiquetage de ses sommets par des entiers naturels distincts pris dans l'ensemble {0,...,m} qui a la propriété que les valeurs absolues des différences des étiquettes des extrémités des arêtes sont toutes distinctes et égales à 1,...,m ; elles identifient ainsi de manière unique les arêtes. Un graphe qui admet un étiquetage gracieux est un graphe gracieux. (fr)
- Грациозная разметка в теории графов — такая вершинная разметка графа с рёбрами некоторым подмножеством целых чисел между 0 и включительно, что разные вершины помечены разными числами, и такая, что, если каждое ребро пометить абсолютной разностью меток вершин, которое оно соединяет, то все полученные разности будут различными. Граф, который допускает грациозную разметку, называется грациозным графом. (ru)
- Граціозна розмітка в теорії графів — така вершинна розмітка графу з ребрами деякою підмножиною цілих чисел між 0 і включно, що різні вершини позначено різними числами, і така, що, якщо кожне ребро позначити абсолютною різницею міток вершин, які воно з'єднує, то всі отримані різниці будуть різними. Граф, який допускає граціозну розмітку, називають граціозним графом. Автором терміна «граціозна розмітка» є Соломон Ґоломб; Александер Роса був першим, хто виділив цей клас розміток і ввів його під назвою -розмітка в статті про розмітки графів.. (uk)
|
