Multigraph (original) (raw)
V teorii grafů se termínem multigraf označuje takový graf, jenž obsahuje rovnoběžné hrany. Mezi dvěma uzly grafu tedy může existovat více (stejně orientovaných) hran. Grafy neobsahující rovnoběžné hrany nazýváme prostými grafy.
| Property | Value |
|---|---|
| dbo:abstract | En matemàtiques, i més concretament en teoria de grafs, un multigraf és un graf que pot tenir arestes múltiples (de vegades anomenades també arestes paral·leles); és a dir, arestes que tenen els mateixos vèrtexs incidents. Així, dos vèrtexs poden estar connectats per més d'una aresta. Per a alguns autors, un multigraf no permet l'existència de bucles, i reserven el terme pseudograf per a multigrafs amb bucles. Altres autors permeten que els multigrafs admetin bucles, i consideren com a sinònims els termes "pseudograf" i "multigraf". Existeixen dues nocions diferents d'arestes múltiples: * Arestes sense identitat pròpia: la identitat d'una aresta queda definida únicament pels dos vèrtexs que connecta. En aquest cas, el terme "arestes múltiples" significa que la mateixa aresta pot aparèixer diverses vegades entre aquests dos vèrtexs. * Arestes amb identitat pròpia: les arestes són entitats primitives, igual que els vèrtexs. Quan hi ha arestes múltiples que connecten dos vèrtexs, es tracta d'arestes diferents. Un multigraf és diferent d'un hipergraf, que és un graf en el qual una aresta pot connectar qualsevol nombre de vèrtexs, no només dos. (ca) V teorii grafů se termínem multigraf označuje takový graf, jenž obsahuje rovnoběžné hrany. Mezi dvěma uzly grafu tedy může existovat více (stejně orientovaných) hran. Grafy neobsahující rovnoběžné hrany nazýváme prostými grafy. (cs) En teoría de grafos, un multigrafo o grafo multivariado es una generalización de un grafo que permite aristas múltiples, o equivalentemente, más de un conjunto de aristas. De esta forma, dos nodos pueden estar conectados por más de una arista. Algunos autores permiten que los multigrafos tengan bucles, es decir, que una arista conecte a un nodo consigo mismo. Un pseudografo se puede definir como un sinónimo de multigrafo, aunque en ocasiones también se utiliza para distinguir a los multigrafos en general, de aquellos que permiten bucles. Si se consideran aristas dirigidas, al multigrafo también se le conoce como multigrafo dirigido o multidigrafo. También se puede hablar de grafo complejo en oposición a un grafo simple (esto es, un grafo sin bucles ni aristas múltiples), como un grafo que posee bucles y/o al menos un par de vértices con más de una arista. (es) In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. There are two distinct notions of multiple edges: * Edges without own identity: The identity of an edge is defined solely by the two nodes it connects. In this case, the term "multiple edges" means that the same edge can occur several times between these two nodes. * Edges with own identity: Edges are primitive entities just like nodes. When multiple edges connect two nodes, these are different edges. A multigraph is different from a hypergraph, which is a graph in which an edge can connect any number of nodes, not just two. For some authors, the terms pseudograph and multigraph are synonymous. For others, a pseudograph is a multigraph that is permitted to have loops. (en) In matematica e in particolare in teoria dei grafi, per multigrafo si intende una struttura che può dirsi costituita da un insieme finito di vertici e da spigoli che collegano due vertici o un vertice con sé stesso (in tal caso lo spigolo si dice cappio), con la possibilità che due vertici siano collegati da più spigoli distinti (e che un vertice presenti più cappi distinti). I multigrafi servono come modelli di sistemi di località e di strade che li collegano per trattare ; in tali modelli i cappi potrebbero essere inutili, oppure potrebbero indicare strade che da una località maggiore portano a località minori e tornano al centro di partenza. Nelle applicazioni effettive i multigrafi vengono arricchiti con parametri che potrebbero indicare lunghezze di strade o importanza delle località. Le formule di struttura delle molecole, in particolare di quelle organiche, sono dei multigrafi con i vertici muniti di etichette che sono simboli di elementi chimici o di gruppi di atomi. (it) 그래프 이론에서 다중 그래프(多重graph, 영어: multigraph 멀티그래프[*])는 두 꼭짓점 사이에 여러 변이 허용되는, 그래프의 일반화이다. (ko) Multigraf (także: pseudograf) – graf, w którym mogą występować krawędzie wielokrotne (powtarzające się) oraz pętle (krawędzie, których końcami jest ten sam wierzchołek). (pl) Multigrafo ou pseudografo é um grafo não dirigido que pode possuir arestas múltiplas (ou paralelas), ou seja, arestas com mesmos nós finais. Assim, dois vértices podem estar conectados por mais de uma aresta. Formalmente, um multigrafo G é um par ordenado , sendo * um conjunto de vértices ou nós, * um multiconjunto de pares não-ordenados de vértices, chamado arestas ou linhas. Alguns autores também consideram multigrafos aqueles que têm laços, isto é, uma aresta que conecta um vértice a ele mesmo; outros chamam estes de pseudografos, reservando o termo multigrafo para os casos em que não há laços. Multigrafos podem ser usados, por exemplo, pra modelar as possíveis conexões de voos oferecidas por uma linha aérea. Nesse caso o pseudografo seria um grafo dirigido com pares de arestas paralelas dirigidas conectando cidades para mostrar que é possível voar para e a partir destas locações. Um multidigrafo é um digrafo (grafo com arestas direcionadas) em que pode-se ter arestas múltiplas. Um multidigrafo é um par ordenado , sendo * um conjunto de vértices ou nós, * um multiconjunto de pares ordenados de vértices, chamado arestas dirigidas, arcos ou flechas. Um multigrafo misto pode ser definido do mesmo jeito que um grafo misto (com arestas que podem ser dirigidas ou não). (pt) В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две). Существует два различных способа обозначения рёбер мультиграфа. Некоторые говорят, что, как и в случае графов без кратных рёбер, ребро определяется вершинами, которые оно соединяет, но каждое ребро может повторяться несколько раз. Другие определяют рёбра равноправными с вершинами элементами графа и они должны иметь собственную идентификацию. (ru) В теорії графів мультиграфом (або псевдографом) називають граф, в якому допускається наявність кратних ребер (їх також називають «паралельними»), тобто є ребра, які мають одні й ті ж кінцеві вершини. Таким чином, дві вершини можуть бути з'єднані більш ніж одним ребром (цим мультиграфи відрізняються від гіперграфів, в яких кожне ребро може з'єднувати будь-яке число вершин, а не рівно дві). Існує два методи позначення ребер мультиграфу. Деякі говорять, що, як і в випадку графів без кратних ребер, ребро визначається вершинами, які воно з'єднує, але кожне ребро може повторюватися декілька разів. Інші визначають ребра рівноправними з вершинами елементами графу і вони повинні мати власну ідентифікацію. (uk) 在数学中，更具体地为在图论中， 重图，也称多重图（multigraph）或伪图（pseudograph）是一个允许有重边（也称多重边，平行边）的图。重边即两个顶点之间可能存在多条边。 每一对顶点之间至多有两条重边的图叫2-重图（2-multigraph）。 重边有两种不同的类型: * 边没有身份:边的身份仅由其两端頂點定义。这种情况下，术语“重边”表示同一条边在两个节点间多次出现。 * 边有身份:边与节点一样是基本实体。当多条边连接两个节点时，这些边是不同的边。 重图与超图不同，超图是指一条边可以连接任意数量的节点，而不是两个。 一些学术文章中，伪图和重图是同义词。另一些则认为伪图是允许有自环的重图。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Multi-pseudograph.svg?width=300 |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=iq0sSnIxJioC&dq=pseudograph&pg=PA6 |
| dbo:wikiPageID | 1774970 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Graph_(Graphentheorie) |
| dbo:wikiPageLength | 8434 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110855191 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Extensions_and_generalizations_of_graphs dbr:Mathematics dbr:Multidimensional_network dbr:Glossary_of_graph_theory dbr:Glossary_of_graph_theory_terms dbr:Graph_(discrete_mathematics) dbr:Graph_labeling dbr:Mixed_graph dbr:Multiset dbr:Ordered_pair dbr:Tuple dbr:Directed_graph dbr:Graduate_Texts_in_Mathematics dbr:Graph_theory dbr:Quiver_(mathematics) dbr:Hypergraph dbr:Triple_(mathematics) dbr:Category_(mathematics) dbr:Category_theory dbr:Set_(mathematics) dbr:Loop_(graph_theory) dbr:Vertex_(graph_theory) dbr:Multiple_edges dbr:Labeled_graph dbr:File:Multi-pseudograph.svg |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Cite_book dbt:Cite_journal dbt:DADS dbt:Redirect-distinguish dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Extensions_and_generalizations_of_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | owl:Thing dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | V teorii grafů se termínem multigraf označuje takový graf, jenž obsahuje rovnoběžné hrany. Mezi dvěma uzly grafu tedy může existovat více (stejně orientovaných) hran. Grafy neobsahující rovnoběžné hrany nazýváme prostými grafy. (cs) 그래프 이론에서 다중 그래프(多重graph, 영어: multigraph 멀티그래프[*])는 두 꼭짓점 사이에 여러 변이 허용되는, 그래프의 일반화이다. (ko) Multigraf (także: pseudograf) – graf, w którym mogą występować krawędzie wielokrotne (powtarzające się) oraz pętle (krawędzie, których końcami jest ten sam wierzchołek). (pl) 在数学中，更具体地为在图论中， 重图，也称多重图（multigraph）或伪图（pseudograph）是一个允许有重边（也称多重边，平行边）的图。重边即两个顶点之间可能存在多条边。 每一对顶点之间至多有两条重边的图叫2-重图（2-multigraph）。 重边有两种不同的类型: * 边没有身份:边的身份仅由其两端頂點定义。这种情况下，术语“重边”表示同一条边在两个节点间多次出现。 * 边有身份:边与节点一样是基本实体。当多条边连接两个节点时，这些边是不同的边。 重图与超图不同，超图是指一条边可以连接任意数量的节点，而不是两个。 一些学术文章中，伪图和重图是同义词。另一些则认为伪图是允许有自环的重图。 (zh) En matemàtiques, i més concretament en teoria de grafs, un multigraf és un graf que pot tenir arestes múltiples (de vegades anomenades també arestes paral·leles); és a dir, arestes que tenen els mateixos vèrtexs incidents. Així, dos vèrtexs poden estar connectats per més d'una aresta. Per a alguns autors, un multigraf no permet l'existència de bucles, i reserven el terme pseudograf per a multigrafs amb bucles. Altres autors permeten que els multigrafs admetin bucles, i consideren com a sinònims els termes "pseudograf" i "multigraf". Existeixen dues nocions diferents d'arestes múltiples: (ca) En teoría de grafos, un multigrafo o grafo multivariado es una generalización de un grafo que permite aristas múltiples, o equivalentemente, más de un conjunto de aristas. De esta forma, dos nodos pueden estar conectados por más de una arista. Algunos autores permiten que los multigrafos tengan bucles, es decir, que una arista conecte a un nodo consigo mismo. Un pseudografo se puede definir como un sinónimo de multigrafo, aunque en ocasiones también se utiliza para distinguir a los multigrafos en general, de aquellos que permiten bucles. Si se consideran aristas dirigidas, al multigrafo también se le conoce como multigrafo dirigido o multidigrafo. También se puede hablar de grafo complejo en oposición a un grafo simple (esto es, un grafo sin bucles ni aristas múltiples), como un grafo (es) In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. There are two distinct notions of multiple edges: A multigraph is different from a hypergraph, which is a graph in which an edge can connect any number of nodes, not just two. For some authors, the terms pseudograph and multigraph are synonymous. For others, a pseudograph is a multigraph that is permitted to have loops. (en) In matematica e in particolare in teoria dei grafi, per multigrafo si intende una struttura che può dirsi costituita da un insieme finito di vertici e da spigoli che collegano due vertici o un vertice con sé stesso (in tal caso lo spigolo si dice cappio), con la possibilità che due vertici siano collegati da più spigoli distinti (e che un vertice presenti più cappi distinti). Le formule di struttura delle molecole, in particolare di quelle organiche, sono dei multigrafi con i vertici muniti di etichette che sono simboli di elementi chimici o di gruppi di atomi. (it) В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две). (ru) Multigrafo ou pseudografo é um grafo não dirigido que pode possuir arestas múltiplas (ou paralelas), ou seja, arestas com mesmos nós finais. Assim, dois vértices podem estar conectados por mais de uma aresta. Formalmente, um multigrafo G é um par ordenado , sendo * um conjunto de vértices ou nós, * um multiconjunto de pares não-ordenados de vértices, chamado arestas ou linhas. Um multidigrafo é um digrafo (grafo com arestas direcionadas) em que pode-se ter arestas múltiplas. Um multidigrafo é um par ordenado , sendo (pt) В теорії графів мультиграфом (або псевдографом) називають граф, в якому допускається наявність кратних ребер (їх також називають «паралельними»), тобто є ребра, які мають одні й ті ж кінцеві вершини. Таким чином, дві вершини можуть бути з'єднані більш ніж одним ребром (цим мультиграфи відрізняються від гіперграфів, в яких кожне ребро може з'єднувати будь-яке число вершин, а не рівно дві). (uk) |
| rdfs:label | Multigraf (ca) Multigraf (cs) Multigraph (de) Multigrafo (es) Multigrafo (it) 다중 그래프 (ko) Multigraph (en) Multigraf (pl) Multigrafo (pt) Мультиграф (ru) 重图 (zh) Мультиграф (uk) |
| owl:differentFrom | dbr:Pseudepigraph |
| owl:sameAs | freebase:Multigraph yago-res:Multigraph wikidata:Multigraph dbpedia-bg:Multigraph dbpedia-ca:Multigraph dbpedia-cs:Multigraph dbpedia-de:Multigraph dbpedia-es:Multigraph dbpedia-fa:Multigraph dbpedia-he:Multigraph dbpedia-hr:Multigraph dbpedia-hu:Multigraph dbpedia-it:Multigraph dbpedia-ko:Multigraph dbpedia-pl:Multigraph dbpedia-pt:Multigraph dbpedia-ru:Multigraph dbpedia-sl:Multigraph http://ta.dbpedia.org/resource/பல்கோட்டுரு dbpedia-uk:Multigraph dbpedia-vi:Multigraph dbpedia-zh:Multigraph https://global.dbpedia.org/id/2Utsb |
| prov:wasDerivedFrom | wikipedia-en:Multigraph?oldid=1110855191&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Multi-pseudograph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Multigraph |
| is dbo:wikiPageDisambiguates of | dbr:Multigraph_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Pseudograph dbr:Multidigraph dbr:Multigraph_(mathematics) dbr:Mixed_multigraph dbr:Directed_multigraph dbr:Labeled_multidigraph dbr:Labeled_multigraph dbr:Underlying_digraph |
| is dbo:wikiPageWikiLink of | dbr:Power_set dbr:Pseudograph dbr:List_of_data_structures dbr:Multigraph_(disambiguation) dbr:Path_coloring dbr:Bicircular_matroid dbr:Petersen_family dbr:Cycle_basis dbr:Vadim_G._Vizing dbr:Vizing's_theorem dbr:Degree_(graph_theory) dbr:Double_Cut_and_Join_Model dbr:Doubly_triangular_number dbr:Induced_subgraph dbr:Intertwingularity dbr:Pseudoforest dbr:Matroid_parity_problem dbr:Multidimensional_network dbr:Rotation_system dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_labeling dbr:Graph_minor dbr:Multiset dbr:Line_graph dbr:Logic_of_graphs dbr:Calculus_on_finite_weighted_graphs dbr:Chinese_postman_problem dbr:Complement_graph dbr:Petri_net dbr:Polygraph_(mathematics) dbr:Spanning_tree dbr:Matrix_addition dbr:Matroid dbr:Tree_(data_structure) dbr:Karger's_algorithm dbr:Adjacency_matrix dbr:Cyclic_group dbr:Dual_graph dbr:Edge_coloring dbr:Eulerian_path dbr:Expander_graph dbr:Overlapping_markup dbr:Digraph_realization_problem dbr:Dinitz_conjecture dbr:Goldberg–Seymour_conjecture dbr:Graph_isomorphism_problem dbr:Graph_property dbr:Graph_theory dbr:Handshaking_lemma dbr:Covering_graph dbr:Hypergraph dbr:Social_learning_network dbr:Abelian_sandpile_model dbr:Chimane_language dbr:LCF_notation dbr:Bipartite_graph dbr:Collaboration_graph dbr:Dipole_graph dbr:Grid_bracing dbr:Christofides_algorithm dbr:Yele_language dbr:Kirchhoff's_theorem dbr:Loop_(graph_theory) dbr:SPQR_tree dbr:Shuffle-exchange_network dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Shannon_multigraph dbr:Random_regular_graph dbr:Multidigraph dbr:Multigraph_(mathematics) dbr:Five_room_puzzle dbr:NGSI-LD dbr:Nauru_graph dbr:Whitney's_planarity_criterion dbr:Quartic_graph dbr:Multiple_edges dbr:Series–parallel_graph dbr:Wagner's_theorem dbr:Sparsity_matroid dbr:Mixed_multigraph dbr:Directed_multigraph dbr:Labeled_multidigraph dbr:Labeled_multigraph dbr:Underlying_digraph |
| is gold:hypernym of | dbr:Latin-script_multigraph dbr:Dipole_graph |
| is foaf:primaryTopic of | wikipedia-en:Multigraph |
