ГРАФЫ АПОЛЛОНИЯ на Английском - Английский перевод

• apollonian networks

Примеры использования Графы аполлония на Русском языке и их переводы на Английский язык

Другое свойство, характеризующее графы Аполлония, связано со связностью.
Another characterization of the Apollonian networks involves their connectivity.

Поскольку графы Аполлония определяются рекурсивным подразделением треугольников, они имеют другие математические описания.
As well as being defined by recursive subdivision of triangles, the Apollonian networks have several other equivalent mathematical characterizations.

Такео ошибочно утверждал, что все графы Аполлония имеют гамильтоновы циклы, однако граф Голднера- Харари служит контрпримером.
Takeo(1960) claimed erroneously that all Apollonian networks have Hamiltonian cycles; however, the Goldner-Harary graph provides a counterexample.

В любом подграфе графа Аполлония последняя добавленная вершина имеет степень три, так что графы Аполлония имеют вырождение три.
In every subgraph of an Apollonian network, the most recently added vertex has degree at most three, so Apollonian networks have degeneracy three.

Другие авторы использовали термин для более широкого класса графов, планарных 3- деревьев, с целью обобщения модели на случайные графы Аполлония.
Other authors applied the same name more broadly to planar 3-trees in their work generalizing the model of Andrade et al. to random Apollonian networks.

Графы Аполлония- это планарные вершинно 3- связные графы, и потому, по теореме Штайница, могут быть всегда представлены как графы выпуклых многогранников.
Apollonian networks are planar 3-connected graphs and therefore, by Steinitz's theorem, can always be represented as the graphs of convex polyhedra.

Хордальный граф, в котором все максимальные клики и все минимальные кликовые сепараторы имеют один и тот же размер, является k- деревом, а графы Аполлония являются примерами 3- деревьев.
A chordal graph in which all maximal cliques and all minimal clique separators have the same size is a k-tree, and Apollonian networks are examples of 3-trees.

Графы Аполлония можно эквивалентно определить как планарные 3- деревья, как максимальные планарные хордальные графы, как однозначно 4- раскрашиваемые планарные графы или как графы блоковых многогранников.
Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes.

Порядок, в котором вершины добавляются при создании графа, таким образом, являются порядком вырождения и графы Аполлония совпадают с 3- вырожденными максимальными планарными графами..
The order in which the vertices are added to create the network is therefore a degeneracy ordering, and the Apollonian networks coincide with the 3-degenerate maximal planar graphs.

Например, графы трехмерных блоковых многогранников- это в точности графы Аполлония, то есть графы, полученные из треугольника путем многократного деления треугольной грани на три меньших треугольника.
For instance, the graphs of three-dimensional stacked polyhedra are exactly the Apollonian networks, the graphs formed from a triangle by repeatedly subdividing a triangular face of the graph into three smaller triangles.

Граница общего числа клик довольно просто следует из границы числа теугольних подграфов и подграфов K4 и приведена в явном виде у Вуда( Wood 2007), который использовал графы Аполлония в качестве примера, показывающего строгость границы.
The bound on the total number of cliques follows easily from the bounds on triangles and K4 subgraphs, and is also stated explicitly by Wood(2007), who provides an Apollonian network as an example showing that this bound is tight.

Графы Аполлония не образуют семейство графов, замкнутого относительно операции взятия миноров графа, так как при удалении ребер, но не вершин, получим граф, не являющийся графом Аполлония.
The Apollonian networks do not form a family of graphs that is closed under the operation of taking graph minors, as removing edges but not vertices from an Apollonian network produces a graph that is not an Apollonian network..

См. статью Нишизеки( Nishizeki 1980) с примером негамильтонов графа, имеющего жесткость 1 и статью Беме, Харанта и Ткача( Böhme, Harant, Tkáč 1999) с доказательством, что графы Аполлония с большей жесткостью являются гамильтоновыми.
See Nishizeki(1980) for a 1-tough non-Hamiltonian example, Böhme, Harant& Tkáč(1999) for the proof that Apollonian networks with greater toughness are Hamiltonian, and Gerlach(2004) for an extension of this result to a wider class of planar graphs.

В экстремальной теории графов графы Аполлония- это в точности планарные графы с n вершинами, в которых число блоков достигает максимального значения n- 3, и планарные графы, в которых число треугольником максимально и равно 3n- 8.
In extremal graph theory, Apollonian networks are also exactly the n-vertex planar graphs in which the number of blocks achieves its maximum, n- 3, and the planar graphs in which the number of triangles achieves its maximum, 3n- 8.

Если граф Аполлония имеет жесткость, большую единицы( что означает, что при удалении любого числа вершин из графа в графе остается связных компонент меньше, чем число удаленных вершин), он обязательно гамильтонов, но существуют негамильтоновы графы Аполлония, если жесткость равна единице Задачу комбинаторики подсчета аполлониевых триангуляций изучал Такео.
If an Apollonian network has toughness greater than one(meaning that removing any set of vertices from the graph leaves a smaller number of connected components than the number of removed vertices) then it necessarily has a Hamiltonian cycle, but there exist non-Hamiltonian Apollonian networks whose toughness is equal to one.

Основываясь на их работе, другие авторы предложили случайные графы Аполлония, получаемые случайным выбором грани для деления, и показали, что для этих графов выполняется степенной закон в распределении степеней вершин, а также показали, что эти графы имеют малые расстояния.
Based on their work, other authors introduced random Apollonian networks, formed by repeatedly choosing a random face to subdivide, and they showed that these also obey power laws in their degree distribution and have small average distances.

Графы Аполлония являются примерами максимальными планарными графами, в которые нельзя добавить ребро без нарушения планарности, или, эквивалентно, графами, которые могут быть нарисованы на плоскости так, что любая грань( включая внешнюю грань) является треугольником.
Apollonian networks are examples of maximal planar graphs, graphs to which no additional edges can be added without destroying planarity, or equivalently graphs that can be drawn in the plane so that every face(including the outer face) is a triangle.

Хотя сами по себе графы Аполлония не могут иметь совершенных паросочетаний, двойственные графам Аполлония графы являются 3- регулярными графами без разрезающих ребер, так что по теореме Петерсена они обязательно имеют по меньшей мере одно совершенное паросочетание.
Although Apollonian networks themselves may not have perfect matchings, the planar dual graphs of Apollonian networks are 3-regular graphs with no cut edges, so by a theorem of Petersen(1891) they are guaranteed to have at least one perfect matching.

Таким образом, граф Аполлония может быть охарактеризован как планарный граф с единственной 4- цветной раскраской.
Therefore, Apollonian networks may also be characterized as the uniquely 4-colorable planar graphs.

Любой граф Аполлония имеет единственную 4- цветную раскраску.
Every Apollonian network is also a uniquely 4-colorable graph.

Тем не менее, семейство планарных частичных 3- деревьев, подграфов графов Аполлония, является минорно замкнутым семейством.
However, the planar partial 3-trees, subgraphs of Apollonian networks, are minor-closed.

Один из методов построения графов Аполлония- начать с трех взаимно касающихся окружностей и многократно вписывать другую окружность в промежуток, образованный тремя окружностями.
One method of constructing Apollonian networks is to start with three mutually-tangent circles and then repeatedly inscribe another circle within the gap formed by three previously-drawn circles.

Граф Аполлония- это максимальный планарный граф, в котором все блоки изоморфны полному графу K4.
An Apollonian network is a maximal planar graph in which all of the blocks are isomorphic to the complete graph K4.

Подобно этому, вырожденность любого внешнепланарного графа не превосходит двух, а вырожденность графов Аполлония равна трем.
Similarly, every outerplanar graph has degeneracy at most two, and the Apollonian networks have degeneracy three.

Другой, более сложный граф Аполлония, использовал Нишизеки как пример 1- жесткого негамильтонова максимального планарного графа..
Another more complicated Apollonian network was used by Nishizeki(1980) to provide an example of a 1-tough non-Hamiltonian maximal planar graph.

Граф Аполлония- это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника.
An Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles.

Это свойство дает альтернативное описание графов Аполлония- это в точности хордальные максимальные планарные графы или, эквивалентно, хордальные полиэдральные графы..
This forms an alternative characterization of the Apollonian networks: they are exactly the chordal maximal planar graphs or equivalently the chordal polyhedral graphs.

Например, существует 12 графов Аполлония с 6 вершинами- три образуются разбиением внешнего треугольника с последующим разбиением двух из полученных треугольников и еще девять образуются разбиением внешнего треугольника и разбиением одного из полученных треугольников с последующим разбиением одного из маленьких треугольников.
For instance, there are 12 6-vertex Apollonian networks: three formed by subdividing the outer triangle once and then subdividing two of the resulting triangles, and nine formed by subdividing the outer triangle once, subdividing one of its triangles, and then subdividing one of the resulting smaller triangles.

Граф Аполлония может быть получен из треугольного графа, вложенного в евклидову плоскость, путем неоднократного выбора треугольной грани вложения, добавления новой вершины в эту треугольную грань и соединения новой вершины с каждой вершиной внутри грани.
An Apollonian network may be formed, starting from a single triangle embedded in the Euclidean plane, by repeatedly selecting a triangular face of the embedding, adding a new vertex inside the face, and connecting the new vertex to each vertex of the face containing it.

У Биркгофа есть ранняя статья, в которой используется двойственная форма графов Аполлония, планарные карты, образованные многократным помещением новых областей в вершинах более простых карт, в качестве примера класса планарных графов с малым числом цветов.
Birkhoff(1930) is an early paper that uses a dual form of Apollonian networks, the planar maps formed by repeatedly placing new regions at the vertices of simpler maps, as a class of examples of planar maps with few colorings.