Symmetric graph
http://dbpedia.org/resource/Symmetric_graph an entity of type: Abstraction100002137
En matematiko, arko-transitiva grafeo estas grafeo G tia ke por ĉiuj du lateroj e1 = u1v1 kaj e2 = u2v2 de G, estas du f : G → G, g : G → G tiaj ke f (e1) = e2, g (e1) = e2 kaj f (u1) = u2, f (v1) = v2g (u1) = v2, g (v1) = u2 En aliaj vortoj, grafeo estas arko-transitiva se ĝia aŭtomorfia grupo agas transitive sur ĝia arkoj.
rdf:langString
어떤 그래프 에 대해, 변의 연결 상태를 보존하는 자기동형사상 가 존재할 경우, 그 사상을 그래프의 대칭성이라고 정의한다. 여기에서 연결 상태를 보존한다는 의미는, 그래프 에 속하는 변 , 에 대해, 가 성립한다는 의미이다. 대칭성이 존재하는 그래프를 대칭 그래프(symmetric graph)라고 부른다. 정의를 확장해서, 어떤 그래프에 대해서 길이가 인 호(arc)를 보존하지만 길이가 인 호를 보존하지는 않는 자기동형사상이 있을 경우, 그 그래프는 -arc-transitive라고 부른다. 변은 길이가 1인 호이므로, 대칭 그래프는 1-arc-transitive 그래프와 같은 의미이다.
rdf:langString
En el campo matemático de la teoría de grafos, un grafo G es simétrico si, dado cualquier par de pares de vértices adyacentes u1—v1 y u2—v2 de G, existe un automorfismo f: V(G) → V(G) tal que f(u1) = u2 and f(v1) = v2. En otras palabras, un grafo es simétrico si su grupo automórfico actúa transitivamente sobre pares ordenados de vértices adyacentes (es decir, sobre los bordes considerados como teniendo una dirección). Este grafo se denomina a veces también 1-arco-transitivo.
rdf:langString
In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism such that and In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive.
rdf:langString
En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif.
rdf:langString
数学のグラフ理論の分野において、あるグラフ G が対称グラフ（たいしょうぐらふ、英: symmetric graph）あるいは弧推移グラフであるとは、G に含まれる任意の与えられた隣接する頂点同士からなるペア u1—v1 および u2—v2 に対して、 f(u1) = u2 and f(v1) = v2 であるような f : V(G) → V(G) が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上（すなわち、方向を持つと考えられる辺の上）で推移的に作用することを言う。 そのようなグラフはしばしば1-弧推移的（1-arc-transitive）あるいは旗推移的（flag-transitive）とも呼ばれる。 定義に従い（u1 と u2 を無視することで）、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、a—b が d—c ではなく c—d へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。
rdf:langString
No campo da matemática da teoria dos grafos, um grafo G é simétrico (ou arco-transitivo) se, dados quaisquer dois pares de vértices ligados u1—v1 e u2—v2 de G , há um automorfismo f : V(G) → V(G) tal que f(u1) = u2 and f(v1) = v2. Em outras palavras, um grafo é simétrico se seu grupo de automorfismo age transitivamente em pares ordenados de vértices ligados (isto é, sobre as arestas consideradas como tendo um sentido). Tal grafo é chamado às vezes também 1-arco-transitivo ou flag-transitivo.
rdf:langString
В теорії графів, граф G є симетричним (або дуго-транзитивним) якщо, для будь-яких пар суміжних вершин u1—v1 і u2—v2 графа G, існує автоморфізм f : V(G) → V(G) такий, що f(u1) = u2 and f(v1) = v2. Інакше кажучи, граф симетричний, якщо група його автоморфізмів діє транзитивно над впорядкованими парами суміжних вершин (тобто, над орієнтованими ребрами). Такий граф іноді називають 1-дуго-транзитивний або прапорцево-транзитивний.
rdf:langString
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм: f : V(G) → V(G) такой, что: f(u1) = u2 and f(v1) = v2. Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах смежных вершин (таким образом, на всех рёбрах, как если бы они имели ориентацию). Такие графы иногда называют также 1-транзитивными относительно дуг или флаг-транзитивными.
rdf:langString
rdf:langString
Arko-transitiva grafeo
rdf:langString
Grafo simétrico
rdf:langString
Graphe symétrique
rdf:langString
대칭 그래프
rdf:langString
対称グラフ
rdf:langString
Symmetric graph
rdf:langString
Grafo simétrico
rdf:langString
Симметричный граф
rdf:langString
Симетричний граф
xsd:integer
1577896
xsd:integer
1094199150
rdf:langString
En matematiko, arko-transitiva grafeo estas grafeo G tia ke por ĉiuj du lateroj e1 = u1v1 kaj e2 = u2v2 de G, estas du f : G → G, g : G → G tiaj ke f (e1) = e2, g (e1) = e2 kaj f (u1) = u2, f (v1) = v2g (u1) = v2, g (v1) = u2 En aliaj vortoj, grafeo estas arko-transitiva se ĝia aŭtomorfia grupo agas transitive sur ĝia arkoj.
rdf:langString
En el campo matemático de la teoría de grafos, un grafo G es simétrico si, dado cualquier par de pares de vértices adyacentes u1—v1 y u2—v2 de G, existe un automorfismo f: V(G) → V(G) tal que f(u1) = u2 and f(v1) = v2. En otras palabras, un grafo es simétrico si su grupo automórfico actúa transitivamente sobre pares ordenados de vértices adyacentes (es decir, sobre los bordes considerados como teniendo una dirección). Este grafo se denomina a veces también 1-arco-transitivo. Por definición (ignorando u1 y u2), un grafo simétrico sin vértices aislados también debe ser . Ya que la definición anterior mapea un borde al otro, una grafo simétrico también debe ser . Sin embargo, un grafo arista transitivo no es necesariamente simétrico, ya que a—b puede mapear a c—d, pero no a d—c. Los , por ejemplo, son arista transitivos y regulares, pero no vértice transitivos. Cada grafo simétrico conectado debe por lo tanto ser a la vez vértice transitivo y arista transitivo, y lo contrario es cierto para los grafos de grado impar. Sin embargo, para los grafos de grado par, existen grafos conectados que son vértice transitivos y arista transitivos, pero no simétricos. Tales grafos son llamados . el grafo semi-transitivo conectado más pequeño es el , de grado 4 y con 27 vértices. Confusamente, algunos autores usan el término "grafo simétrico" hablando de grafos que son vértice transitivos y arista transitivos, pero no son arco transitivos. Una definición así incluiría los grafos semi-transitivos, que están excluidos en virtud de la definición anterior. Un grafo distancia-transitivo es aquel donde en lugar de considerar pares de vértices adyacentes (es decir, los vértices separados por una arista), la definición comprende dos pares de vértices, cada uno a la misma distancia. Tales grafos son automáticamente simétricos, por definición. Un t-arco es definido como una secuencia de t+1 vértices, tal que dos vértices consecutivos cualesquiera en la secuencia son adyacentes, y cualquier vértice repetido está separado por lo menos 2 pasos. Un grafo t-transitivo es un grafo tal que el grupo automórfico actúa transitivamente sobre t-arcos, pero no sobre (t+1)-arcos. Ya que 1-arcos son simplemente aristas, cada grafo simétrico de grado 3 o mayor debe ser t-transitivo para alguna t, y el valor de t puede ser usado para clasificar los grafos simétricos. Por ejemplo, el cubo es 2-transitivo.
rdf:langString
En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Par définition, un graphe symétrique sans sommet isolé est sommet-transitif et arête-transitif. La distinction entre arête-transitif et arc-transitif est subtile: « Arête-transitif » signifie que pour toute paire d'arêtes et , il existe un automorphisme qui envoie l'une sur l'autre, donc tel que , alors que « arc-transitif » demande qu'en plus et que, pour un autre automorphisme , on ait . Si un graphe est arête-transitif sans être 1-transitif, alors toute arête peut être envoyée sur toute autre, mais seulement d'une seule parmi les deux façons possibles. Le terme « symétrique » est d'ailleurs parfois employé pour désigner un graphe qui soit simplement arête-transitif et sommet-transitif ; cette utilisation du terme est ambiguë, car il existe des graphes qui sont arête-transitifs et sommet-transitifs sans être arc-transitifs. Ces graphes sont rares : le plus petit exemple est le graphe de Doyle. Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif.
rdf:langString
In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism such that and In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive. By definition (ignoring u1 and u2), a symmetric graph without isolated vertices must also be vertex-transitive. Since the definition above maps one edge to another, a symmetric graph must also be edge-transitive. However, an edge-transitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Star graphs are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example, semi-symmetric graphs are edge-transitive and regular, but not vertex-transitive. Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree. However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric. Such graphs are called half-transitive. The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices. Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above. A distance-transitive graph is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition. A t-arc is defined to be a sequence of t + 1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A t-transitive graph is a graph such that the automorphism group acts transitively on t-arcs, but not on (t + 1)-arcs. Since 1-arcs are simply edges, every symmetric graph of degree 3 or more must be t-transitive for some t, and the value of t can be used to further classify symmetric graphs. The cube is 2-transitive, for example.
rdf:langString
어떤 그래프 에 대해, 변의 연결 상태를 보존하는 자기동형사상 가 존재할 경우, 그 사상을 그래프의 대칭성이라고 정의한다. 여기에서 연결 상태를 보존한다는 의미는, 그래프 에 속하는 변 , 에 대해, 가 성립한다는 의미이다. 대칭성이 존재하는 그래프를 대칭 그래프(symmetric graph)라고 부른다. 정의를 확장해서, 어떤 그래프에 대해서 길이가 인 호(arc)를 보존하지만 길이가 인 호를 보존하지는 않는 자기동형사상이 있을 경우, 그 그래프는 -arc-transitive라고 부른다. 변은 길이가 1인 호이므로, 대칭 그래프는 1-arc-transitive 그래프와 같은 의미이다.
rdf:langString
数学のグラフ理論の分野において、あるグラフ G が対称グラフ（たいしょうぐらふ、英: symmetric graph）あるいは弧推移グラフであるとは、G に含まれる任意の与えられた隣接する頂点同士からなるペア u1—v1 および u2—v2 に対して、 f(u1) = u2 and f(v1) = v2 であるような f : V(G) → V(G) が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上（すなわち、方向を持つと考えられる辺の上）で推移的に作用することを言う。 そのようなグラフはしばしば1-弧推移的（1-arc-transitive）あるいは旗推移的（flag-transitive）とも呼ばれる。 定義に従い（u1 と u2 を無視することで）、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、a—b が d—c ではなく c—d へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。 したがって、全ての連結対称グラフは頂点推移的かつ辺推移的であり、次数が奇数であるようなグラフに対してはその逆も成立する。しかしながら、次数が偶数である場合は、頂点推移的かつ辺推移的であるが、対称でないような連結グラフも存在する。そのようなグラフは（half-transitive）であると呼ばれる。最小の連結半推移グラフは、次数4で頂点数27のである。厄介なことに、学者の中には対称グラフという語を、弧推移グラフではなく、頂点推移的かつ辺推移的であるようなグラフに対して用いる人もいる。そのような定義では、上述の定義では除外されている半推移グラフを含むことになる。 距離推移グラフでは、隣接している頂点同士のペア（すなわち、距離が1だけ離れている頂点のペア）を考える代わりに、各々が同じ距離だけ離れているペアを考える。そのようなグラフは、定義より、自然に対称グラフとなる。 t-弧という語が、「t + 1 個の頂点からなる列で、その列において連続するどの二つの頂点も必ずグラフ上で隣接し、かつ繰り返し現れる頂点については必ず二段階以上離れているもの」に対して定義される。t-推移グラフとは、その自己同型群がt-弧の上では推移的に作用するが (t+1)-弧の上ではそのように作用しないグラフのことを言う。1-弧は単純に辺であるため、次数が3以上であるような全ての対称グラフには、t-推移的となるような t が必ず存在し、そのような t の値は対称グラフを分類する際に用いられる。例えば、立方体は2-推移的である。
rdf:langString
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм: f : V(G) → V(G) такой, что: f(u1) = u2 and f(v1) = v2. Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах смежных вершин (таким образом, на всех рёбрах, как если бы они имели ориентацию). Такие графы иногда называют также 1-транзитивными относительно дуг или флаг-транзитивными. По определению симметричные графы без изолированных вершин должны быть также вершинно-транзитивными. Поскольку по определению выше рёбра можно перевести из одного в другое, симметричные графы должны быть также рёберно-транзитивными. Однако рёберно-транзитивный граф не обязательно симметричен, поскольку a—b может быть переведён в c—d, но не в d—c. Полусимметричные графы, например, являются рёберно-транзитивными и регулярными, но не вершинно-транзитивными. Любой связный симметричный граф должен быть как вершинно-транзитивен, так и рёберно-транзитивен, и обратное верно для графов нечётной степени. Однако для чётных степеней существуют связные одновременно вершинно-транзитивные и рёберно-транзитивные графы, но не симметричные. Такие графы называются полутранзитивными. Наименьший связный полутранзитивный граф — это граф Холта, имеющий степень 4 и 27 вершин. Запутывает то, что некоторые авторы используют термин «симметричный граф» для графов, которые одновременно являются вершинно-транзитивными и рёберно-транзитивными. Такое определение включает полутранзитивные графы, которые исключены определением выше. Дистанционно-транзитивный граф — это граф, в котором вместо единичного расстояния смежные вершины находятся на одном и том же фиксированном расстоянии. Такие графы по определению симметричны. t-дуга определяется как последовательность t+1 вершин, таких, что любые две последовательные вершины смежны, и повторение вершин может произойти не раньше, чем через 2 шага. Граф называется t-транзитивным, если группа автоморфизмов действует транзитивно на t-дуги, но не на (t+1)-дуги. Поскольку 1-дуги — это просто рёбра, любой симметричный граф степени 3 и более должен быть t-транзитивным для некоторого t, и значение t можно использовать для классификации графов. Куб является 2-транзитивным, например.
rdf:langString
В теорії графів, граф G є симетричним (або дуго-транзитивним) якщо, для будь-яких пар суміжних вершин u1—v1 і u2—v2 графа G, існує автоморфізм f : V(G) → V(G) такий, що f(u1) = u2 and f(v1) = v2. Інакше кажучи, граф симетричний, якщо група його автоморфізмів діє транзитивно над впорядкованими парами суміжних вершин (тобто, над орієнтованими ребрами). Такий граф іноді називають 1-дуго-транзитивний або прапорцево-транзитивний. За визначенням (ігноруючи u1 і u2), симетричний граф без ізольованих вершин має також бути вершинно-транзитивним. Завдяки визначенню через відображення одного ребра на інше, симетричний граф має також бути реберно-транзитивним. Однак, реберно-транзитивний граф не має бути симетричним, бо a—b можуть відбиватись в c—d, але не в d—c. Наприклад, напівсиметричний граф є реберно-транзитивним і регулярним, але не вершинно-транзитивним. Таким чином, кожний зв'язний симетричний граф має бути і вершинно-транзитивним, і реберно-транзитивним, зворотне твердження теж правильне для графів непарних степенів. Однак, для парних степенів, існують зв'язні вершинно-транзитивні і реберно-транзитивні, але не симетричні графи. Такі графи називаються . Найменший зв'язний напівтранзитивний граф це , зі степенем 4 і 27 вершинами. Деякі автори використовують термін «симетричний граф» для позначення графів, що вершинно-транзитивні і реберно-транзитивні, радше ніж дуго-транзитивні. Таке визначення охоплює напівтранзитивні графи, які виключені визначенням поданим вище. У відстанево-транзитивного графа замість розглядання пар суміжних вершин (тобто вершин на відстані 1), визначення розглядає дві пари вершин, кожна з однаковою відстанню між вершинами. Такий граф автоматично симетричний за визначенням. Визначимо t-дугу як послідовність з t+1 вершин таких, що будь-які дві послідовні вершини суміжні, з допустимою відстанню між вершинами, що повторюються, більшою за два кроки. T-транзитивний граф це такий граф, що група автоморфізмів діє транзитивно на t-дугах, але не на (t+1)-дугах. Через те, що 1-дуги це просто ребра, кожний симетричний граф степені 3 або більше має бути t-транзитивний для деякого t, і значення t можна використати для подальшої класифікації симетричних графів. Куб є 2-транзитивним, наприклад.
rdf:langString
No campo da matemática da teoria dos grafos, um grafo G é simétrico (ou arco-transitivo) se, dados quaisquer dois pares de vértices ligados u1—v1 e u2—v2 de G , há um automorfismo f : V(G) → V(G) tal que f(u1) = u2 and f(v1) = v2. Em outras palavras, um grafo é simétrico se seu grupo de automorfismo age transitivamente em pares ordenados de vértices ligados (isto é, sobre as arestas consideradas como tendo um sentido). Tal grafo é chamado às vezes também 1-arco-transitivo ou flag-transitivo. Por definição (ignorando u1 e u2), um grafo simétrico sem vértices isolados deve também ser vértice-transitivo. Como a definição acima mapeia uma aresta a outra, um grafo simétrico também deve ser aresta-transitivo. Contudo, um grafo aresta-transitivo não precisa ser simétrico, uma vez que a—b pode mapear a c—d, mas não a d—c. Grafos simétricos, por exemplo, aão aresta-transitivos e regulares, mas não vértice-transitivos. Todo grafo simétrico conexo deve, portanto, ser tanto vértice-transitivo quanto aresta-transitivo, e o inverso é verdadeiro para grafos de grau ímpar. No entanto, para graus pares, existem grafos conectados que são vértice-transitivos e aresta-transitivos, mas não simétricos. Tais grafos são denominados meio-transitivos. O menor grafo conexo meio-transitiva é o grafo de Holt, com grau 4 e 27 vértices. De forma confusa, alguns autores usam o termo "grafo simétrico" para significar um grafo que é vértice-transitivo e aresta-transitivo, ao invés de um grafo arco-transitivo. Tal definição inclui grafos meio-transitivos, que são excluídos pela definição acima. Um grafo distância-transitivo é aquele em que em vez de considerar pares de vértices ligados (i.e. vértices a uma distância de um), a definição abrange dois pares de vértices, cada um à mesma distância. Tais grafos são automaticamente simétricos, por definição. Um t-arco é definido como uma sequência de t+1 vértices ligados, com quaisquer vértices repetidos estando a mais de 2 passos distante. Um grafo t-transitivo é um grafo tal que o grupo de automorfismo atua transitivamente nos t-arcos, mas não nos (t+1)-arcos. Uma vez que os 1-arcos são simplesmente arestas, qualquer grafo simétrico de grau 3 ou superior tem que ser t-transitivo para algum t, e o valor de t pode ser usado para além disso classificar grafos simétricos. O cubo é 2-transitivo, por exemplo.
xsd:nonNegativeInteger
11348
