| 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)
|
| has 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
