Star (graph theory) (original) (raw)
Hvězda je v teorii grafů označení takových grafů, které mají jednoduchou podobu jediného centrálního vrcholu a na něj napojených listů. Jedná se tedy zároveň o strom a zároveň o úplný bipartitní graf. Hvězda o listech bývá značena buď jako bipartitní graf , nebo je pro ni používána zvláštní značka . V rámci síťové topologie odpovídá hvězda hvězdicové topologii.
| Property | Value |
|---|---|
| dbo:abstract | Hvězda je v teorii grafů označení takových grafů, které mají jednoduchou podobu jediného centrálního vrcholu a na něj napojených listů. Jedná se tedy zároveň o strom a zároveň o úplný bipartitní graf. Hvězda o listech bývá značena buď jako bipartitní graf , nebo je pro ni používána zvláštní značka . V rámci síťové topologie odpovídá hvězda hvězdicové topologii. (cs) Ein Sterngraph, kurz Stern, ist in der Graphentheorie eine Klasse von Graphen einfacher Struktur. In einem Sterngraph ist ein zentraler Knoten mit allen anderen Knoten durch Kanten verbunden, während die anderen Knoten neben diesem zentralen Knoten keine weiteren Nachbarn besitzen. Sterngraphen mit Kanten werden mit oder bezeichnet. Eine Netzwerktopologie in Form eines Sterngraphen wird Stern-Topologie genannt. (de) En grafeteorio, stelgrafeo (mallonge stelo) Sk estas plena dukolora grafeo K1,k, t.e., arbo kun unusola interna vertico kaj k folioj (aŭ 0 interna vertico kaj k + 1 folioj, kiam k ≤ 1). (eo) En teoría de grafos, una estrella Sk es el grafo bipartito completo K1,k, un árbol con un vértice interno y k hojas. Una estrella con 3 aristas se conoce en inglés como claw (garra o garfio). La estrella Sk es transitiva en aristas, tiene una distancia de 1 y un diámetro de 2, girth ∞, índice cromático k y número cromático 2. Las estrellas pueden también describirse como los únicos grafos conexos en que a lo más un vértice tiene grado mayor que uno. (es) In graph theory, a star Sk is the complete bipartite graph K1,k : a tree with one internal node and k leaves (but no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define Sk to be the tree of order k with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves. A star with 3 edges is called a claw. The star Sk is edge-graceful when k is even and not when k is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when l > 1), girth ∞ (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0). Additionally, the star has large automorphism group, namely, the symmetric group on k letters. Stars may also be described as the only connected graphs in which at most one vertex has degree greater than one. (en) En mathématiques, et plus particulièrement en théorie des graphes, une étoile Sk est le graphe biparti complet K1,k. (fr) スター もしくは星Sk は、グラフ理論の用語の1つであり、ただ1つの頂点とそれにつながる k 個の葉のみを持つグラフである。また、スターは完全2部グラフ K1, kでもある。スター Sk を直径が2で次数が k である木とする人も存在し、この場合 2 < k であり葉の数は k-1 である。 頂点が3個の星は特別にクローもしくは爪と呼ぶ。 スター Sk は k が偶数のときには edge-graceful であり、 k が奇数の場合はそうでない。スターは頂点推移グラフであり、 1 < k においてグラフの直径は2であり、内周は ∞ である。また、スターは自己同型群を持つ。すなわち、 k 次の対称群である。 スターは、（最大でも）1つの頂点の次数が1より大きい、連結グラフともいえる。 (ja) Inom grafteori är en stjärngraf Sk den kompletta bipartita grafen K1,k: ett träd med en intern nod och k blad (löv) för k>1, men utan interna noder och med k + 1 blad för k ≤ 1. Vissa författare definierar däremot Sk som trädet av ordning k med största diameter 2, i vilket fall en stjärngraf med k>2 i stället har k − 1 blad. En stjärngraf med tre kanter kallas klograf. En stjärngraf kan också beskrivas som en graf med högst en nod som har en högre grad än ett.En stjärngraf är en tändsticksgraf, har ett kromatiskt tal som är 2 och ett som är k. Prüfersekvensen för en orotad märkt stjärngraf K1,k består av k − 1 upprepningar av centralnoden. (sv) Em teoria dos grafos, uma estrela Sk é o grafo bipartido completo K1,k, uma árvore com um nó interno e k folhas. Uma estrela com 3 arestas é chamada uma garra. A estrela Sk é quando k é par e não quando k é ímpar. Ela é , e têm diâmtero 2, cintura ∞, índice cromático k e número cromático 2. Estrelas também podem ser descritas como os únicos grafos conectados em que no máximo um vértice tem grau maior que um. (pt) 在图论中，星（英語：Star）Sk属于完全二分图K1,k：是具有一个内部节点和k个叶节点的树（但当k≤1时，没有内部节点且由k+1个叶节点）。另外，一些文章将Sk 定义为最大直径为2的k阶树；在这种情况下，k>2的星具有k−1个叶节点。 有三条边的星又称为爪。 当k是偶数时，星Sk是，当k是奇数时则不是。它是一个的，其直径为2（当k > 1时），围长为∞（无循环结构），色指数为k，色数为2（当k > 0时）。此外，星具有较大的自同构群，即k个字母上的对称群。 星也可以被描述为仅有的最多只有一个顶点的度大于1的连通图。 (zh) Граф-звезда — связный граф в котором всё рёбра исходят из одной вершины.Звезда с вершиной обычно обозначается , при этом называют порядком звезды. (ru) У теорії графів зірка Sk (англ. star) — це повний двочастковий граф K1,k: дерево з єдиним внутрішнім вузлом і k листками (але при k ≤ 1 має k+1 листків і не має внутрішніх вузлів). Крім того, деякі автори визначають Sk як дерево порядку k з максимальною відстанню 2; в цьому випадку зірка k > 2 має k − 1 листок. Зірка з 3-ма ребрами називається клешнею. Зірка Sk називається , коли k парне і не є такою, коли непарне. Вона є реберно-транзитивною сірниковому графу, і має відстань 2 (при k>1), обхват ∞ (не має циклів), хроматичний індекс k і хроматичне число 2 (при k> 0). Крім того, зірка має велику групу автоморфізмів, а саме симетричну групу з k букв. Зірка також може бути описана, як зв'язний граф, в якому не більше однієї вершини, що має степінь більше одиниці. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Star_network_7.svg?width=300 |
| dbo:wikiPageID | 19310129 (xsd:integer) |
| dbo:wikiPageLength | 7450 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123232938 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Arboricity dbr:Unit_distance_graph dbr:Degree_(graph_theory) dbr:Induced_subgraph dbr:Prüfer_sequence dbr:Complete_bipartite_graph dbr:Computer_network dbr:Chromatic_number dbr:Girth_(graph_theory) dbr:Order_(graph_theory) dbr:Line_graph dbr:Star_network dbr:Claw-free_graph dbr:Star_(simplicial_complex) dbc:Trees_(graph_theory) dbr:Tree_(graph_theory) dbr:Distributed_computing dbr:Edge-graceful_labeling dbr:Edge-transitive_graph dbr:Euclidean_space dbc:Parametric_families_of_graphs dbr:Diameter_(graph_theory) dbr:Graph_isomorphism dbr:Graph_theory dbr:Isometry dbr:Bipartite_graph dbr:Tropical_geometry dbr:Branchwidth dbr:Whitney_graph_isomorphism_theorem dbr:Graph_invariant dbr:Metric_space dbr:Chromatic_index dbr:Matchstick_graph dbr:Star_coloring dbr:Edge-transitive dbr:File:Star_graphs.svg dbr:File:Star_network_7.svg |
| dbp:chromaticNumber | 2 (xsd:integer) |
| dbp:diameter | 2 (xsd:integer) |
| dbp:imageCaption | The star . (en) |
| dbp:name | Star (en) |
| dbp:properties | dbr:Unit_distance_graph dbr:Tree_(graph_theory) dbr:Edge-transitive_graph dbr:Bipartite_graph |
| dbp:spectralGap | 1 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Commonscat dbt:Infobox_graph dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Sub |
| dct:subject | dbc:Trees_(graph_theory) dbc:Parametric_families_of_graphs |
| gold:hypernym | dbr:K |
| rdf:type | dbo:School yago:WikicatParametricFamiliesOfGraphs yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | Hvězda je v teorii grafů označení takových grafů, které mají jednoduchou podobu jediného centrálního vrcholu a na něj napojených listů. Jedná se tedy zároveň o strom a zároveň o úplný bipartitní graf. Hvězda o listech bývá značena buď jako bipartitní graf , nebo je pro ni používána zvláštní značka . V rámci síťové topologie odpovídá hvězda hvězdicové topologii. (cs) Ein Sterngraph, kurz Stern, ist in der Graphentheorie eine Klasse von Graphen einfacher Struktur. In einem Sterngraph ist ein zentraler Knoten mit allen anderen Knoten durch Kanten verbunden, während die anderen Knoten neben diesem zentralen Knoten keine weiteren Nachbarn besitzen. Sterngraphen mit Kanten werden mit oder bezeichnet. Eine Netzwerktopologie in Form eines Sterngraphen wird Stern-Topologie genannt. (de) En grafeteorio, stelgrafeo (mallonge stelo) Sk estas plena dukolora grafeo K1,k, t.e., arbo kun unusola interna vertico kaj k folioj (aŭ 0 interna vertico kaj k + 1 folioj, kiam k ≤ 1). (eo) En teoría de grafos, una estrella Sk es el grafo bipartito completo K1,k, un árbol con un vértice interno y k hojas. Una estrella con 3 aristas se conoce en inglés como claw (garra o garfio). La estrella Sk es transitiva en aristas, tiene una distancia de 1 y un diámetro de 2, girth ∞, índice cromático k y número cromático 2. Las estrellas pueden también describirse como los únicos grafos conexos en que a lo más un vértice tiene grado mayor que uno. (es) En mathématiques, et plus particulièrement en théorie des graphes, une étoile Sk est le graphe biparti complet K1,k. (fr) スター もしくは星Sk は、グラフ理論の用語の1つであり、ただ1つの頂点とそれにつながる k 個の葉のみを持つグラフである。また、スターは完全2部グラフ K1, kでもある。スター Sk を直径が2で次数が k である木とする人も存在し、この場合 2 < k であり葉の数は k-1 である。 頂点が3個の星は特別にクローもしくは爪と呼ぶ。 スター Sk は k が偶数のときには edge-graceful であり、 k が奇数の場合はそうでない。スターは頂点推移グラフであり、 1 < k においてグラフの直径は2であり、内周は ∞ である。また、スターは自己同型群を持つ。すなわち、 k 次の対称群である。 スターは、（最大でも）1つの頂点の次数が1より大きい、連結グラフともいえる。 (ja) Em teoria dos grafos, uma estrela Sk é o grafo bipartido completo K1,k, uma árvore com um nó interno e k folhas. Uma estrela com 3 arestas é chamada uma garra. A estrela Sk é quando k é par e não quando k é ímpar. Ela é , e têm diâmtero 2, cintura ∞, índice cromático k e número cromático 2. Estrelas também podem ser descritas como os únicos grafos conectados em que no máximo um vértice tem grau maior que um. (pt) 在图论中，星（英語：Star）Sk属于完全二分图K1,k：是具有一个内部节点和k个叶节点的树（但当k≤1时，没有内部节点且由k+1个叶节点）。另外，一些文章将Sk 定义为最大直径为2的k阶树；在这种情况下，k>2的星具有k−1个叶节点。 有三条边的星又称为爪。 当k是偶数时，星Sk是，当k是奇数时则不是。它是一个的，其直径为2（当k > 1时），围长为∞（无循环结构），色指数为k，色数为2（当k > 0时）。此外，星具有较大的自同构群，即k个字母上的对称群。 星也可以被描述为仅有的最多只有一个顶点的度大于1的连通图。 (zh) Граф-звезда — связный граф в котором всё рёбра исходят из одной вершины.Звезда с вершиной обычно обозначается , при этом называют порядком звезды. (ru) In graph theory, a star Sk is the complete bipartite graph K1,k : a tree with one internal node and k leaves (but no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define Sk to be the tree of order k with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves. A star with 3 edges is called a claw. Stars may also be described as the only connected graphs in which at most one vertex has degree greater than one. (en) Inom grafteori är en stjärngraf Sk den kompletta bipartita grafen K1,k: ett träd med en intern nod och k blad (löv) för k>1, men utan interna noder och med k + 1 blad för k ≤ 1. Vissa författare definierar däremot Sk som trädet av ordning k med största diameter 2, i vilket fall en stjärngraf med k>2 i stället har k − 1 blad. En stjärngraf med tre kanter kallas klograf. En stjärngraf kan också beskrivas som en graf med högst en nod som har en högre grad än ett.En stjärngraf är en tändsticksgraf, har ett kromatiskt tal som är 2 och ett som är k. (sv) У теорії графів зірка Sk (англ. star) — це повний двочастковий граф K1,k: дерево з єдиним внутрішнім вузлом і k листками (але при k ≤ 1 має k+1 листків і не має внутрішніх вузлів). Крім того, деякі автори визначають Sk як дерево порядку k з максимальною відстанню 2; в цьому випадку зірка k > 2 має k − 1 листок. Зірка з 3-ма ребрами називається клешнею. Зірка також може бути описана, як зв'язний граф, в якому не більше однієї вершини, що має степінь більше одиниці. (uk) |
| rdfs:label | Hvězda (graf) (cs) Sterngraph (de) Stelgrafeo (grafeteorio) (eo) Estrella (teoría de grafos) (es) Graphe étoile (fr) スター (グラフ理論) (ja) Star (graph theory) (en) Estrela (teoria dos grafos) (pt) Граф-звезда (ru) Stjärngraf (sv) 星 (图论) (zh) Зірка (теорія графів) (uk) |
| owl:sameAs | freebase:Star (graph theory) yago-res:Star (graph theory) wikidata:Star (graph theory) dbpedia-cs:Star (graph theory) dbpedia-de:Star (graph theory) dbpedia-eo:Star (graph theory) dbpedia-es:Star (graph theory) dbpedia-fr:Star (graph theory) dbpedia-hu:Star (graph theory) dbpedia-ja:Star (graph theory) dbpedia-pt:Star (graph theory) dbpedia-ru:Star (graph theory) dbpedia-sl:Star (graph theory) dbpedia-sv:Star (graph theory) http://ta.dbpedia.org/resource/விண்மீன்_கோட்டுரு dbpedia-uk:Star (graph theory) dbpedia-zh:Star (graph theory) https://global.dbpedia.org/id/2S4kX |
| prov:wasDerivedFrom | wikipedia-en:Star_(graph_theory)?oldid=1123232938&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Star_graphs.svg wiki-commons:Special:FilePath/Star_network_7.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Star_(graph_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Star_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Claw_(graph_theory) dbr:Star_graph |
| is dbo:wikiPageWikiLink of | dbr:Wiener_index dbr:Bipartite_half dbr:Book_embedding dbr:Dessin_d'enfant dbr:Arboricity dbr:Petersen_family dbr:Vizing's_conjecture dbr:Molecular_geometry dbr:Zero-divisor_graph dbr:1-center_problem dbr:Complete_bipartite_graph dbr:Matching_in_hypergraphs dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Graph_coloring_game dbr:Branch-decomposition dbr:Equitable_coloring dbr:Erdős–Gyárfás_conjecture dbr:Star_network dbr:Steiner_tree_problem dbr:Halin_graph dbr:Planar_separator_theorem dbr:Split_(graph_theory) dbr:Star_(disambiguation) dbr:Matroid_minor dbr:Tree_(graph_theory) dbr:Windmill_graph dbr:Gallery_of_named_graphs dbr:Link_(simplicial_complex) dbr:Spectral_graph_theory dbr:Edge_coloring dbr:Euclidean_minimum_spanning_tree dbr:Forbidden_graph_characterization dbr:Pairwise_independence dbr:Centrality dbr:Graham–Pollak_theorem dbr:Claw_(graph_theory) dbr:Tree-depth dbr:Power_graph_analysis dbr:Uniquely_colorable_graph dbr:Kevin_de_Queiroz dbr:Symmetric_graph dbr:Dimension_(graph_theory) dbr:Dominating_set dbr:Book_(graph_theory) dbr:Greedy_embedding dbr:Ramsey's_theorem dbr:Unit_disk_graph dbr:Gyárfás–Sumner_conjecture dbr:Universal_vertex dbr:Sumner's_conjecture dbr:Simultaneous_embedding dbr:Sparse_network dbr:Star_graph |
| is foaf:primaryTopic of | wikipedia-en:Star_(graph_theory) |
