Girth (graph theory) (original) (raw)
في نظرية الرسومات ، مقاس محيط ( المقاس أختصارا) (girth) رسم بياني هو طول أقصر دورة في الرسم البياني. إذا كان الرسم البياني لا يحتوي على أي دورات (أي أنه رسم بياني بدون دوره، فسيتم تعريف المقاس بأنه اللانهاية . على سبيل المثال، دورة طولها4 (تاخذ شكل المربع) بها مقاس المحيط 4 وقياس محيط المثلث يساوي 4 أيضا، وشبكة الثلاثي لديها حزام 3. فبالتالي أي رسم بياني به طول محيطه يساوي أربعة أو أكثر يعتبر رسم بدون مثلثات .
| Property | Value |
|---|---|
| dbo:abstract | في نظرية الرسومات ، مقاس محيط ( المقاس أختصارا) (girth) رسم بياني هو طول أقصر دورة في الرسم البياني. إذا كان الرسم البياني لا يحتوي على أي دورات (أي أنه رسم بياني بدون دوره، فسيتم تعريف المقاس بأنه اللانهاية . على سبيل المثال، دورة طولها4 (تاخذ شكل المربع) بها مقاس المحيط 4 وقياس محيط المثلث يساوي 4 أيضا، وشبكة الثلاثي لديها حزام 3. فبالتالي أي رسم بياني به طول محيطه يساوي أربعة أو أكثر يعتبر رسم بدون مثلثات . (ar) In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity.For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free. (en) En teoría de grafos, la cintura (en inglés girth) de un grafo no dirigido es la longitud del ciclo más corto contenido en dicho grafo. Si el grafo no posee ciclos (es decir, es un grafo acíclico), su cintura se define como infinita. Por ejemplo, un ciclo de cuatro vértices (cuadrado) tiene cintura 4. Un látice cuadrado tiene cintura 4. Una malla triangular tiene cintura 3. Si un grafo tiene contura mayor a tres, se dice que es libre de triángulos. * El grafo de Petersen tiene cintura 5 * El grafo de Heawood tiene cintura de 6 * El grafo de McGee tiene cintura 7 * El grafo de Tutte-Coxeter tiene cintura 8 (es) En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de −1). (fr) 그래프 이론과 매트로이드 이론에서 안둘레(영어: girth 거스[*])는 그래프 또는 매트로이드 속의 가장 작은 “구멍”, 즉 최소의 순환의 크기이다. 마찬가지로 그래프 또는 매트로이드의 밖둘레(영어: circumference 서컴퍼런스[*])는 최대의 순환의 크기이다. (ko) Nella teoria dei grafi, il calibro (in inglese girth) di un grafo è la lunghezza del ciclo più corto contenuto nel grafo. Se il grafo non contiene alcun ciclo (è cioè un grafo aciclico), il suo calibro si definisce infinito.Ad esempio, un ciclo di ordine 4 (quadrato) ha calibro 4. Anche una griglia ha calibro 4, e una maglia triangolare ha calibro 3. Un grafo con calibro pari a 4 o superiore è . (it) 数学のグラフ理論の分野における内周（ないしゅう、英: girth）とは、グラフに含まれる最小の閉路の長さのことを言う。もしもグラフが閉路を含まないなら（すなわち、無閉路グラフであるなら）、その内周は無限大と定義される。例えば、（平方）4-閉路グラフの内周は4である。格子グラフの内周も4である。三角形メッシュの内周は3である。内周が4以上のグラフは、である。 (ja) Talia grafu (ang. girth) – długość najkrótszego cyklu zawartego w grafie. Przyjmuje się, że obwód grafów acyklicznych jest równy nieskończoności. Np. cykl o długości 4 ma obwód równy 4, tak jak wszystkie . * K3, obwód 3 * K4, obwód 3 * Graf Petersena, obwód 5 * , obwód 6 * , obwód 8 (pl) Em teoria dos grafos a cintura ou girth de um grafo é o comprimento do mais curto ciclo contido no grafo. Se o grafo não contém ciclos (isto é, um grafo acíclico), a sua cintura é definida como infinita. Por exemplo, um 4-ciclo (quadrado), tem cintura 4. Uma grade tem cintura 4, igualmente, e uma malha triangular tem cintura 3. Um grafo com cintura >3 é livre de triângulos. (pt) Обхват графа — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности.Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников. (ru) Обхват в теорії графів — довжина найкоротшого циклу, що міститься в заданому графі. Якщо граф не містить циклів (тобто є ациклічним графом), його обхват за визначенням дорівнює нескінченності.Наприклад, 4-цикл (квадрат) має обхват 4. Квадратна ґратка має також обхват 4, а трикутна сітка має обхват 3. Граф з обхватом чотири і більше не містить трикутників. (uk) 在图论中，一個圖的圍長定義為這個圖所包含的最短環長。 若這個圖是，它的圍長則定義做無窮大。 舉例來說，4-環（正方形）的圍長是 4。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Petersen1_tiny.svg?width=300 |
| dbo:wikiPageID | 12013 (xsd:integer) |
| dbo:wikiPageLength | 5459 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1114774710 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probabilistic_method dbr:Mycielskian dbr:Paul_Erdős dbr:Cubic_graph dbr:Cycle_(graph_theory) dbr:Undirected_graph dbr:Independent_set_(graph_theory) dbc:Graph_invariants dbr:Petersen_graph dbr:Chromatic_number dbr:Cage_(graph_theory) dbr:Harries–Wong_graph dbr:McGee_graph dbr:Triangle-free_graph dbr:Heawood_graph dbr:K-edge-connected_graph dbr:Linear_group dbr:Dual_graph dbr:Expander_graph dbr:Finite_field dbr:Cayley_graph dbr:Graph_theory dbr:Graphic_matroid dbr:Matroid_girth dbr:Harries_graph dbr:Balaban_10-cage dbr:Systolic_geometry dbr:Planar_graph dbr:Grötzsch_graph dbr:Infinity dbr:Forest_(graph_theory) dbr:Tutte–Coxeter_graph dbr:Random_graph dbr:Tutte_eight_cage dbr:Ramanujan_graphs dbr:Matroid_theory |
| dbp:wikiPageUsesTemplate | dbt:Frac dbt:Main dbt:Math dbt:Mvar dbt:Short_description dbt:Visible_anchor |
| dcterms:subject | dbc:Graph_invariants |
| gold:hypernym | dbr:Length |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants dbo:Album |
| rdfs:comment | في نظرية الرسومات ، مقاس محيط ( المقاس أختصارا) (girth) رسم بياني هو طول أقصر دورة في الرسم البياني. إذا كان الرسم البياني لا يحتوي على أي دورات (أي أنه رسم بياني بدون دوره، فسيتم تعريف المقاس بأنه اللانهاية . على سبيل المثال، دورة طولها4 (تاخذ شكل المربع) بها مقاس المحيط 4 وقياس محيط المثلث يساوي 4 أيضا، وشبكة الثلاثي لديها حزام 3. فبالتالي أي رسم بياني به طول محيطه يساوي أربعة أو أكثر يعتبر رسم بدون مثلثات . (ar) In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity.For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free. (en) En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de −1). (fr) 그래프 이론과 매트로이드 이론에서 안둘레(영어: girth 거스[*])는 그래프 또는 매트로이드 속의 가장 작은 “구멍”, 즉 최소의 순환의 크기이다. 마찬가지로 그래프 또는 매트로이드의 밖둘레(영어: circumference 서컴퍼런스[*])는 최대의 순환의 크기이다. (ko) Nella teoria dei grafi, il calibro (in inglese girth) di un grafo è la lunghezza del ciclo più corto contenuto nel grafo. Se il grafo non contiene alcun ciclo (è cioè un grafo aciclico), il suo calibro si definisce infinito.Ad esempio, un ciclo di ordine 4 (quadrato) ha calibro 4. Anche una griglia ha calibro 4, e una maglia triangolare ha calibro 3. Un grafo con calibro pari a 4 o superiore è . (it) 数学のグラフ理論の分野における内周（ないしゅう、英: girth）とは、グラフに含まれる最小の閉路の長さのことを言う。もしもグラフが閉路を含まないなら（すなわち、無閉路グラフであるなら）、その内周は無限大と定義される。例えば、（平方）4-閉路グラフの内周は4である。格子グラフの内周も4である。三角形メッシュの内周は3である。内周が4以上のグラフは、である。 (ja) Talia grafu (ang. girth) – długość najkrótszego cyklu zawartego w grafie. Przyjmuje się, że obwód grafów acyklicznych jest równy nieskończoności. Np. cykl o długości 4 ma obwód równy 4, tak jak wszystkie . * K3, obwód 3 * K4, obwód 3 * Graf Petersena, obwód 5 * , obwód 6 * , obwód 8 (pl) Em teoria dos grafos a cintura ou girth de um grafo é o comprimento do mais curto ciclo contido no grafo. Se o grafo não contém ciclos (isto é, um grafo acíclico), a sua cintura é definida como infinita. Por exemplo, um 4-ciclo (quadrado), tem cintura 4. Uma grade tem cintura 4, igualmente, e uma malha triangular tem cintura 3. Um grafo com cintura >3 é livre de triângulos. (pt) Обхват графа — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности.Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников. (ru) Обхват в теорії графів — довжина найкоротшого циклу, що міститься в заданому графі. Якщо граф не містить циклів (тобто є ациклічним графом), його обхват за визначенням дорівнює нескінченності.Наприклад, 4-цикл (квадрат) має обхват 4. Квадратна ґратка має також обхват 4, а трикутна сітка має обхват 3. Граф з обхватом чотири і більше не містить трикутників. (uk) 在图论中，一個圖的圍長定義為這個圖所包含的最短環長。 若這個圖是，它的圍長則定義做無窮大。 舉例來說，4-環（正方形）的圍長是 4。 (zh) En teoría de grafos, la cintura (en inglés girth) de un grafo no dirigido es la longitud del ciclo más corto contenido en dicho grafo. Si el grafo no posee ciclos (es decir, es un grafo acíclico), su cintura se define como infinita. Por ejemplo, un ciclo de cuatro vértices (cuadrado) tiene cintura 4. Un látice cuadrado tiene cintura 4. Una malla triangular tiene cintura 3. Si un grafo tiene contura mayor a tres, se dice que es libre de triángulos. * El grafo de Petersen tiene cintura 5 * El grafo de Heawood tiene cintura de 6 * El grafo de McGee tiene cintura 7 * (es) |
| rdfs:label | مقاس المحيط (نظرية الرسومات) (ar) Cintura (teoría de grafos) (es) Girth (graph theory) (en) Maille (théorie des graphes) (fr) Calibro (teoria dei grafi) (it) 内周 (グラフ理論) (ja) 안둘레 (ko) Talia grafu (pl) Cintura (teoria dos grafos) (pt) Обхват (теория графов) (ru) Обхват (теорія графів) (uk) 圍長 (圖論) (zh) |
| owl:sameAs | freebase:Girth (graph theory) yago-res:Girth (graph theory) wikidata:Girth (graph theory) dbpedia-ar:Girth (graph theory) dbpedia-es:Girth (graph theory) dbpedia-fa:Girth (graph theory) dbpedia-fr:Girth (graph theory) dbpedia-hr:Girth (graph theory) dbpedia-hu:Girth (graph theory) dbpedia-it:Girth (graph theory) dbpedia-ja:Girth (graph theory) dbpedia-ko:Girth (graph theory) dbpedia-pl:Girth (graph theory) dbpedia-pt:Girth (graph theory) dbpedia-ru:Girth (graph theory) dbpedia-simple:Girth (graph theory) dbpedia-sl:Girth (graph theory) dbpedia-uk:Girth (graph theory) dbpedia-zh:Girth (graph theory) https://global.dbpedia.org/id/56Psd |
| prov:wasDerivedFrom | wikipedia-en:Girth_(graph_theory)?oldid=1114774710&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Petersen1_tiny.svg wiki-commons:Special:FilePath/Heawood_Graph.svg wiki-commons:Special:FilePath/McGee_graph.svg wiki-commons:Special:FilePath/Tutte_eight_cage.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Girth_(graph_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Girth |
| is dbo:wikiPageRedirects of | dbr:Circumference_(graph_theory) dbr:Odd_girth dbr:Girth_of_a_graph |
| is dbo:wikiPageWikiLink of | dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:Desargues_graph dbr:András_Hajnal dbr:List_of_graph_theory_topics dbr:Cycle_(graph_theory) dbr:Cycle_double_cover dbr:Dyck_graph dbr:Dürer_graph dbr:Incidence_geometry dbr:Induced_path dbr:Induced_subgraph dbr:Levi_graph dbr:List_of_graphs_by_edges_and_vertices dbr:Zero-divisor_graph dbr:(a,_b)-decomposition dbr:110-vertex_Iofinova-Ivanov_graph dbr:Configuration_(geometry) dbr:Crossing_number_inequality dbr:Errera_graph dbr:Generalized_polygon dbr:Generalized_quadrangle dbr:Petersen_graph dbr:Circumference_(graph_theory) dbr:Alexandru_Balaban dbr:Friendship_graph dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Graph_coloring_game dbr:Graph_homomorphism dbr:Graph_power dbr:Moore_graph dbr:Cop_number dbr:Arithmetic_group dbr:Cage_(graph_theory) dbr:Snark_(graph_theory) dbr:Star_(graph_theory) dbr:Franklin_graph dbr:Frucht_graph dbr:Horton_graph dbr:Pappus_graph dbr:Planar_separator_theorem dbr:743_(number) dbr:Butterfly_graph dbr:Triangle-free_graph dbr:Well-covered_graph dbr:Distance-transitive_graph dbr:Heawood_graph dbr:K-edge-connected_graph dbr:5 dbr:Dual_graph dbr:Edge_coloring dbr:Pancake_graph dbr:Pancake_sorting dbr:Chvátal_graph dbr:Fano_plane dbr:Folkman_graph dbr:Foster_graph dbr:Goldner–Harary_graph dbr:Graph_property dbr:Gray_graph dbr:Length dbr:Girth dbr:Matroid_girth dbr:Grötzsch's_theorem dbr:Harries_graph dbr:Heilbronn_triangle_problem dbr:Introduction_to_systolic_geometry dbr:Balaban_10-cage dbr:Coxeter_graph dbr:Hypohamiltonian_graph dbr:Laves_graph dbr:Bipartite_graph dbr:Biregular_graph dbr:Symmetric_graph dbr:Systolic_geometry dbr:Hoffman–Singleton_graph dbr:Holt_graph dbr:Thin_group_(combinatorial_group_theory) dbr:Zarankiewicz_problem dbr:Diamond_graph dbr:Bull_graph dbr:Circle_graph dbr:Neil_Robertson_(mathematician) dbr:Odd_graph dbr:Orbifold dbr:Ramanujan_graph dbr:Klein_graphs dbr:F26A_graph dbr:Gyárfás–Sumner_conjecture dbr:Tutte–Coxeter_graph dbr:Triangle_graph dbr:Subcoloring dbr:Odd_girth dbr:Table_of_simple_cubic_graphs dbr:Girth_of_a_graph |
| is foaf:primaryTopic of | wikipedia-en:Girth_(graph_theory) |
