Dense graph (original) (raw)
En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
| Property | Value | ||||
|---|---|---|---|---|---|
| dbo:abstract | En matemàtiques, un graf dens és un graf en què el nombre d'arestes és pròxim al nombre d'arestes màxim que pot tindre el graf. Per contra, un graf amb poques arestes és un graf dispers. La distinció entre dispers i dens és una mica vaga. Una possibilitat és elegir un nombre amb i definir un graf dispers com aquell que |E | = O( | V | k), on | E |
| dbo:wikiPageExternalLink | https://xlinux.nist.gov/dads/HTML/sparsegraph.html | ||||
| dbo:wikiPageID | 2777098 (xsd:integer) | ||||
| dbo:wikiPageLength | 8645 (xsd:nonNegativeInteger) | ||||
| dbo:wikiPageRevisionID | 1123543612 (xsd:integer) | ||||
| dbo:wikiPageWikiLink | dbr:Degeneracy_(graph_theory) dbr:Dense_subgraph dbc:Graph_families dbr:Arboricity dbr:Pseudoforest dbr:Superparticular_ratio dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Mathematics dbr:Graph_(discrete_mathematics) dbr:Bounded_expansion dbr:Erdős–Stone_theorem dbr:Tree_(graph_theory) dbr:Laman_graph dbr:Lecture_Notes_in_Computer_Science dbr:Outerplanar_graph dbr:Directed_graph dbr:Graduate_Texts_in_Mathematics dbr:Biclique-free_graph dbr:Bipartite_graph dbr:Planar_graph dbr:National_Institute_of_Standards_and_Technology dbr:Infimum dbr:Vertex_(graph_theory) dbr:Journal_of_the_London_Mathematical_Society dbr:European_Journal_of_Combinatorics dbr:Rigidity_theory_(structural) dbr:Somewhere_dense_(Graph_Theory) | ||||
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Math dbt:Mvar dbt:Sfrac dbt:Short_description dbt:Abs | ||||
| dct:subject | dbc:Graph_families | ||||
| rdf:type | yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 | ||||
| rdfs:comment | En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte. (fr) 수학에서 밀집 그래프(dense graph)는 간선(변)의 수가 최대 간선의 수에 가까운 그래프이다. 그와 반대로, 간선이 얼마 없는 그래프는 희소 그래프(sparse graph)라고 한다. 밀집과 희소 간의 구별은 다소 모호하므로 문맥에 따라 달라질 수 있다. 방향이 없는 무향 단순 그래프의 경우 그래프 밀도는 다음과 같이 정의된다: 방향이 있는 유향 단순 그래프의 경우, 그래프 밀도는 다음과 같이 정의된다: 여기에서 E는 간선의 수, V는 그래프 안의 정점의 수이다. 무향 그래프의 간선의 최대 수는 이므로 최대 밀도는 1(완전 그래프의 경우)이며 최소 밀도는 0이다. (ko) La densità di un grafo, indicata con è il rapporto tra il numero di archi del grafo rispetto al numero di coppie di nodi. Quindi misura quanti archi ha il grafo rispetto a quanti ne potrebbe avere dati i nodi del grafo. (it) У математиці граф називається щільним, якщо кількість його ребер близька до максимальної. На противагу, граф з малою кількістю ребер називається розрідженим. Різниця між щільним і розпливчатим графом розмита, і залежить від контексту. Для неорієнтованих простих графів густина визначається як: Для орієнтованих графів: де E — кількість ребер, а V — кількість вершин графу. Максимальна кількість ребер для неорієнтованого графу , тому максимальна густина дорівнює 1 (для повних графів), а мінімальна густина дорівнює 0. (uk) Пло́тный граф — граф, в котором число рёбер близко к максимально возможному у полного графа с числом вершин : Граф, имеющий малое число рёбер, принято называть разреженным графом. Вообще говоря, разница между разреженным и плотным графом условна и зависит от контекста. Для неориентированного простого графа (рёберная) плотность графа с числом вершин определяется как отношение числа его рёбер к числу рёбер полного графа: . Максимальное число рёбер равно так что максимальная плотность графа равна 1 (для полных графов) и минимальная равна 0 — для несвязанного графа. (ru) En matemàtiques, un graf dens és un graf en què el nombre d'arestes és pròxim al nombre d'arestes màxim que pot tindre el graf. Per contra, un graf amb poques arestes és un graf dispers. La distinció entre dispers i dens és una mica vaga. Una possibilitat és elegir un nombre amb i definir un graf dispers com aquell que |E | = O( | V | k), on | E |
| rdfs:label | Graf dens (ca) Densidad (teoría de grafos) (es) Dense graph (en) Densità di un grafo (it) Densité d'un graphe (fr) 밀집 그래프 (ko) Плотный граф (ru) Щільний граф (uk) | ||||
| owl:sameAs | freebase:Dense graph yago-res:Dense graph wikidata:Dense graph dbpedia-ca:Dense graph dbpedia-es:Dense graph dbpedia-fa:Dense graph dbpedia-fr:Dense graph dbpedia-hu:Dense graph dbpedia-it:Dense graph dbpedia-ko:Dense graph dbpedia-ru:Dense graph dbpedia-th:Dense graph dbpedia-uk:Dense graph https://global.dbpedia.org/id/2rsCd | ||||
| prov:wasDerivedFrom | wikipedia-en:Dense_graph?oldid=1123543612&ns=0 | ||||
| foaf:isPrimaryTopicOf | wikipedia-en:Dense_graph | ||||
| is dbo:wikiPageRedirects of | dbr:Density_(graph_theory) dbr:Graph_density dbr:Sparse_graph | ||||
| is dbo:wikiPageWikiLink of | dbr:Prim's_algorithm dbr:Bellman–Ford_algorithm dbr:Degeneracy_(graph_theory) dbr:Arboricity dbr:Beta_skeleton dbr:List_of_graph_theory_topics dbr:Unit_distance_graph dbr:Incidence_poset dbr:Independent_set_(graph_theory) dbr:Superparticular_ratio dbr:Crispin_Nash-Williams dbr:Maximum_cardinality_matching dbr:Neighbourhood_(graph_theory) dbr:Social_network_analysis dbr:Clique-width dbr:Clique_problem dbr:Glossary_of_graph_theory dbr:Consumer_network dbr:Equitable_coloring dbr:Claw-free_graph dbr:Clique_(graph_theory) dbr:Øystein_Ore dbr:Feedback_arc_set dbr:Fulkerson_Prize dbr:Hopcroft–Karp_algorithm dbr:Béla_Bollobás dbr:Triangle-free_graph dbr:Widest_path_problem dbr:Karger's_algorithm dbr:Locally_linear_graph dbr:Pancake_graph dbr:Pancake_sorting dbr:Floyd–Warshall_algorithm dbr:Graph_traversal dbr:Graphon dbr:Harborth's_conjecture dbr:Density_(graph_theory) dbr:Szemerédi_regularity_lemma dbr:Hamiltonian_path dbr:Biclique-free_graph dbr:Yoshiharu_Kohayakawa dbr:Directed_acyclic_graph dbr:Graph_density dbr:Strong_orientation dbr:Extremal_graph_theory dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Paley_graph dbr:Zero-suppressed_decision_diagram dbr:Sparse_network dbr:Sparsity_matroid dbr:Twin-width dbr:Sparse_graph | ||||
| is foaf:primaryTopic of | wikipedia-en:Dense_graph |