Graph partition (original) (raw)
Graphpartitionierung bezeichnet die Anwendung geeigneter Algorithmen zur Berechnung von Graphpartitionen (vgl. Schnitt (Graphentheorie)) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.
| Property | Value |
|---|---|
| dbo:abstract | Graphpartitionierung bezeichnet die Anwendung geeigneter Algorithmen zur Berechnung von Graphpartitionen (vgl. Schnitt (Graphentheorie)) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen. (de) In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see .Two common examples of graph partitioning are minimum cut and maximum cut problems. (en) En théorie des graphes et en algorithmique, le partitionnement de graphe est la tâche qui consiste à diviser un graphe orienté ou non orienté en plusieurs parties. Plusieurs propriétés peuvent être recherchées pour ce découpage, par exemple on peut minimiser le nombre d'arêtes liant deux parties différentes. Coupe maximum et Coupe minimum sont deux exemples communs de partitionnement de graphe. (fr) 그래프 분할(graph partitioning) 문제는 수학에서 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이다. 이때 각 부분의 크기는 똑같아야 한다. 이 문제에는 다양한 변형이 있는데, 변마다 가중치를 주어서 가중치의 합이 가장 적게 되는 분할을 찾는 경우, 각 부분의 꼭짓점 수가 일정한 범위 안에서 차이나는 경우도 허용하는 경우 등이 있다. 그래프를 두 부분으로 나누는 문제를 특별히 그래프 이등분(graph bisection) 문제라고 한다. 그래프 분할 문제는 조합 최적화 문제 중에서 어려운 문제로, NP-완전에 속한다. 따라서 그래프 분할 문제의 최적해를 직접 구하기는 힘들고, 근사해를 구하기 위한 방법이 여럿 개발되어 있다. 대표적인 방법으로 과 FM 알고리즘이 있다. (ko) Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причём . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), то есть оценка является завышенной. При значениях числа вершин графа более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется метод ветвей и границ), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов. Необходимость получения разбиения возникает при решении ряда задач: 1. * Задача раскраски графа — каждое множество вершин состоит из вершин одного цвета, причём вершины одного цвета не имеют общих инцидентных рёбер. Обычно интересует отыскание минимальной раскраски, что в общем случае является задачей класса NP (критерий оптимальности — ). 2. * Задача определения числа и состава компонент связности графа. 3. * При проектировании топологии локальной сети её разбиение на широковещательные домены определяется требованиями производительности (критерий оптимальности — объем передаваемого междоменного трафика при использовании различных серверов и сетевых служб (доступ к файловым серверам, службам DHCP, WINS, DNS и т. д.), ограничения — число портов и пропускная способность коммутаторов, маршрутизаторов и каналов связи, а также стоимость). 4. * В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов. 5. * В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой. 6. * Представление графа в виде ярусно-параллельной формы или граф-схемы алгоритма в виде множества сечений (множества вершин в составе сечений могут быть неортогональными). 7. * Разбиение графа алгоритма на непересекающиеся подграфы с последующим их размещением в процессорных элементах или элементах в составе ПЛИС при реализации конвейерной обработки данных (балансировка нагрузки). (ru) Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа у вигляді множини підмножин вершин за певними правилами. Зазвичай за умовою задачі потрібно, щоб , тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому . , більше 15-20 отриманих оптимальних розбиттях як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів. Необхідність отримання розбиття виникає при вирішенні ряду завдань: 1. * Задача розфарбовування графа — кожна множина вершин складається з вершин одного кольору, причому вершини одного кольору не мають спільних інцидентних ребер. Зазвичай цікавить відшукання мінімальної розмальовки, що в загальному випадку є завданням класу NP (критерій оптимальності— ). 2. * Завдання визначення числа і складу компонента зв'язності графа. 3. * Під час проектування топології локальної мережі її розбиття на широкомовні домени визначається вимогами продуктивності (критерій оптимальності — обсяг переданого міждоменного трафіку при використанні різних серверів і мережевих служб (доступ до файлових серверів, служб DHCP, WINS, DNS і т. Д.), Обмеження — число портів і пропускна здатність комутаторів, маршрутизаторів і каналів зв'язку, а також вартість). 4. * У задачі трасування з'єднань друкованих плат або мікросхем необхідно розбиття вихідної схеми на шари (кожен з яких представляє собою планарний граф). Критерії оптимальності — мінімальне число шарів і з'єднань (фактично, собівартість виробництва), обмеження — габаритні розміри і вимоги термічної і електромагнітної сумісності електронних компонентів. 5. * У задачі розбиття граф-схеми алгоритму на блоки з метою реалізації на багатопроцесорної системі або логічному мультиконтроллером. Критерії оптимальності — мінімальне число блоків, мінімальні ступеня дублювання сигналів мікрооперацій і логічних умов, мінімальне число міжмодульних передач управління, мінімальний трафік міжмодульних передач управління і даних; обмеження диктуються використовуваною елементною базою. 6. * Подання графа у вигляді ярусно-паралельної форми або граф-схеми алгоритму у вигляді безлічі перетинів (безлічі вершин у складі перетинів можуть бути неортогональної). 7. * Розбиття графа алгоритму на непересічні підграфи з подальшим їх розміщенням в процесорних елементах або елементах в складі ПЛІС при реалізації конвеєрної обробки даних (балансування навантаження). (uk) Em matemática, o problema de partição de grafos é definido com seus dados na forma de um G = (V,A), com V vértices e A arestas, de tal modo que é possível G em componentes menores com propriedades específicas. Por exemplo, uma partição de k-vias divide o conjunto de vértices em k componentes menores. Uma boa partição é definida como uma em que o número de arestas entre componentes menores é pequeno. Partição Uniforme de um Grafo é um tipo de problema de particionamento de grafo que consiste em dividir um grafo em componentes, no qual os componentes são quase do mesmo tamanho e existem algumas conexões entre esses componentes. Importantes aplicações de particionamento de grafos incluem computação específica, particionando vários estágios de um circuito feito em e agendamento de tarefas em sistemas com multi-processadores. Recentemente, o problema de partição de grafo ganhou importância devido à suas aplicações para clustering e detecção de associações em redes sociais, patológicas e biológicas. Uma pesquisa sobre as recentes tendências em métodos e aplicações computacionais podem ser encontrados em. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Bisected_network.jpg?width=300 |
| dbo:wikiPageExternalLink | http://cebichot.netne.net/graph_partitioning_book/ http://masters.donntu.edu.ua/2006/fvti/krasnokutskaya/library/generals.pdf https://e-collection.library.ethz.ch/view/eth:5739%3Fq=Balanced%20Partitioning%20of%20Grids%20and%20Related%20Graphs https://web.archive.org/web/20081003192033/http:/www.stanford.edu/~dgleich/demos/matlab/spectral/spectral.html http://glaros.dtc.umn.edu/gkhome/node/107 https://www.cs.princeton.edu/~bwk/btl.mirror/partitioning.pdf |
| dbo:wikiPageID | 11973947 (xsd:integer) |
| dbo:wikiPageLength | 30274 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112459019 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scikit-learn dbr:Electronic_design_automation dbr:Algebraic_connectivity dbr:VLSI dbr:Degree_matrix dbc:NP-complete_problems dbr:Conductance_(graph) dbr:Maximum_cut dbr:Eigenvectors dbr:Graph_(discrete_mathematics) dbr:Modularity_(networks) dbr:NP-complete dbr:NP-hard dbr:LOBPCG dbr:METIS dbr:Kernighan–Lin_algorithm dbr:Planar_separator_theorem dbr:Laplacian_matrix dbr:Minimum_cut dbr:Adjacency_matrix dbr:Fiduccia-Mattheyses_algorithm dbr:P=NP dbr:Partition_of_a_set dbr:Cheeger_bound dbr:Graph_partition dbr:Preconditioning dbr:Hamiltonian_mechanics dbr:Hypergraph dbr:ARPACK dbc:Computational_problems_in_graph_theory dbr:Planar_graph dbr:Graph_Laplacian dbr:Finite_element_method dbr:Spectral_clustering dbr:Eigendecomposition dbr:Multigrid dbr:File:Bisected_network.jpg dbr:File:Connected_graph..jpg dbr:File:Graph_comparison.jpg |
| dbp:bot | InternetArchiveBot (en) |
| dbp:date | January 2020 (en) |
| dbp:fixAttempted | yes (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Dead_link dbt:Harvtxt dbt:Main dbt:Radic dbt:Short_description |
| dct:subject | dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| rdfs:comment | Graphpartitionierung bezeichnet die Anwendung geeigneter Algorithmen zur Berechnung von Graphpartitionen (vgl. Schnitt (Graphentheorie)) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen. (de) En théorie des graphes et en algorithmique, le partitionnement de graphe est la tâche qui consiste à diviser un graphe orienté ou non orienté en plusieurs parties. Plusieurs propriétés peuvent être recherchées pour ce découpage, par exemple on peut minimiser le nombre d'arêtes liant deux parties différentes. Coupe maximum et Coupe minimum sont deux exemples communs de partitionnement de graphe. (fr) 그래프 분할(graph partitioning) 문제는 수학에서 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이다. 이때 각 부분의 크기는 똑같아야 한다. 이 문제에는 다양한 변형이 있는데, 변마다 가중치를 주어서 가중치의 합이 가장 적게 되는 분할을 찾는 경우, 각 부분의 꼭짓점 수가 일정한 범위 안에서 차이나는 경우도 허용하는 경우 등이 있다. 그래프를 두 부분으로 나누는 문제를 특별히 그래프 이등분(graph bisection) 문제라고 한다. 그래프 분할 문제는 조합 최적화 문제 중에서 어려운 문제로, NP-완전에 속한다. 따라서 그래프 분할 문제의 최적해를 직접 구하기는 힘들고, 근사해를 구하기 위한 방법이 여럿 개발되어 있다. 대표적인 방법으로 과 FM 알고리즘이 있다. (ko) In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networ (en) Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причём . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, (ru) Em matemática, o problema de partição de grafos é definido com seus dados na forma de um G = (V,A), com V vértices e A arestas, de tal modo que é possível G em componentes menores com propriedades específicas. Por exemplo, uma partição de k-vias divide o conjunto de vértices em k componentes menores. Uma boa partição é definida como uma em que o número de arestas entre componentes menores é pequeno. Partição Uniforme de um Grafo é um tipo de problema de particionamento de grafo que consiste em dividir um grafo em componentes, no qual os componentes são quase do mesmo tamanho e existem algumas conexões entre esses componentes. Importantes aplicações de particionamento de grafos incluem computação específica, particionando vários estágios de um circuito feito em e agendamento de tarefas e (pt) Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа у вигляді множини підмножин вершин за певними правилами. Зазвичай за умовою задачі потрібно, щоб , тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому . , більше 15-20 отриманих оптимальних розбиттях як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів. (uk) |
| rdfs:label | Graphpartitionierung (de) Partitionnement de graphe (fr) Graph partition (en) 그래프 분할 (ko) Partição de grafos (pt) Разбиение графа (ru) Розбиття графа (uk) |
| owl:sameAs | freebase:Graph partition yago-res:Graph partition wikidata:Graph partition dbpedia-de:Graph partition dbpedia-fa:Graph partition dbpedia-fr:Graph partition dbpedia-ko:Graph partition dbpedia-pt:Graph partition dbpedia-ru:Graph partition dbpedia-sr:Graph partition dbpedia-uk:Graph partition https://global.dbpedia.org/id/4Ymyf |
| prov:wasDerivedFrom | wikipedia-en:Graph_partition?oldid=1112459019&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Bisected_network.jpg wiki-commons:Special:FilePath/Connected_graph..jpg wiki-commons:Special:FilePath/Graph_comparison.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_partition |
| is dbo:wikiPageDisambiguates of | dbr:Partition |
| is dbo:wikiPageRedirects of | dbr:Graph_partitioning dbr:Multi-level_technique dbr:Graph_bisection dbr:Graph_bisection_problem dbr:Graph_partitioning_problem dbr:Mutli_level_technique dbr:Partition_of_a_graph dbr:Multi_level_technique |
| is dbo:wikiPageWikiLink of | dbr:Priority_matching dbr:Memetic_algorithm dbr:Bipartite_half dbr:Brian_Kernighan dbr:Algebraic_connectivity dbr:Approximate_max-flow_min-cut_theorem dbr:Arboricity dbr:List_of_graph_theory_topics dbr:DIMACS dbr:Vertex_separator dbr:List_of_partition_topics dbr:Maximum_cut dbr:Network_theory dbr:Multipartite_graph dbr:METIS dbr:Kernighan–Lin_algorithm dbr:PLS_(complexity) dbr:Partition dbr:Planar_separator_theorem dbr:Graph_partitioning dbr:Minimum_cut dbr:Bregman–Minc_inequality dbr:Graph_(abstract_data_type) dbr:Graph_cuts_in_computer_vision dbr:Graph_partition dbr:List_of_NP-complete_problems dbr:Hyperbolic_geometric_graph dbr:Hypergraph dbr:Uniquely_colorable_graph dbr:Multi-level_technique dbr:Modular_decomposition dbr:Split_graph dbr:Fiduccia–Mattheyses_algorithm dbr:Graph_bisection dbr:Graph_bisection_problem dbr:Graph_partitioning_problem dbr:Rainbow-independent_set dbr:Scotch dbr:Extremal_Ensemble_Learning dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:NP-intermediate dbr:Strength_of_a_graph dbr:Streamline_upwind_Petrov–Galerkin_pres...ncompressible_Navier–Stokes_equations dbr:Mutli_level_technique dbr:Partition_of_a_graph dbr:Multi_level_technique |
| is foaf:primaryTopic of | wikipedia-en:Graph_partition |
