Graph partition
http://dbpedia.org/resource/Graph_partition an entity of type: WikicatComputationalProblemsInGraphTheory
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.
rdf:langString
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.
rdf:langString
그래프 분할(graph partitioning) 문제는 수학에서 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이다. 이때 각 부분의 크기는 똑같아야 한다. 이 문제에는 다양한 변형이 있는데, 변마다 가중치를 주어서 가중치의 합이 가장 적게 되는 분할을 찾는 경우, 각 부분의 꼭짓점 수가 일정한 범위 안에서 차이나는 경우도 허용하는 경우 등이 있다. 그래프를 두 부분으로 나누는 문제를 특별히 그래프 이등분(graph bisection) 문제라고 한다. 그래프 분할 문제는 조합 최적화 문제 중에서 어려운 문제로, NP-완전에 속한다. 따라서 그래프 분할 문제의 최적해를 직접 구하기는 힘들고, 근사해를 구하기 위한 방법이 여럿 개발되어 있다. 대표적인 방법으로 과 FM 알고리즘이 있다.
rdf:langString
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
rdf:langString
Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причём . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных,
rdf:langString
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
rdf:langString
Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа у вигляді множини підмножин вершин за певними правилами. Зазвичай за умовою задачі потрібно, щоб , тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому . , більше 15-20 отриманих оптимальних розбиттях як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів.
rdf:langString
rdf:langString
Graphpartitionierung
rdf:langString
Partitionnement de graphe
rdf:langString
Graph partition
rdf:langString
그래프 분할
rdf:langString
Partição de grafos
rdf:langString
Разбиение графа
rdf:langString
Розбиття графа
xsd:integer
11973947
xsd:integer
1112459019
rdf:langString
InternetArchiveBot
rdf:langString
January 2020
rdf:langString
yes
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
그래프 분할(graph partitioning) 문제는 수학에서 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이다. 이때 각 부분의 크기는 똑같아야 한다. 이 문제에는 다양한 변형이 있는데, 변마다 가중치를 주어서 가중치의 합이 가장 적게 되는 분할을 찾는 경우, 각 부분의 꼭짓점 수가 일정한 범위 안에서 차이나는 경우도 허용하는 경우 등이 있다. 그래프를 두 부분으로 나누는 문제를 특별히 그래프 이등분(graph bisection) 문제라고 한다. 그래프 분할 문제는 조합 최적화 문제 중에서 어려운 문제로, NP-완전에 속한다. 따라서 그래프 분할 문제의 최적해를 직접 구하기는 힘들고, 근사해를 구하기 위한 방법이 여럿 개발되어 있다. 대표적인 방법으로 과 FM 알고리즘이 있다.
rdf:langString
Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причём . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), то есть оценка является завышенной. При значениях числа вершин графа более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется метод ветвей и границ), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов. Необходимость получения разбиения возникает при решении ряда задач: 1.
* Задача раскраски графа — каждое множество вершин состоит из вершин одного цвета, причём вершины одного цвета не имеют общих инцидентных рёбер. Обычно интересует отыскание минимальной раскраски, что в общем случае является задачей класса NP (критерий оптимальности — ). 2.
* Задача определения числа и состава компонент связности графа. 3.
* При проектировании топологии локальной сети её разбиение на широковещательные домены определяется требованиями производительности (критерий оптимальности — объем передаваемого междоменного трафика при использовании различных серверов и сетевых служб (доступ к файловым серверам, службам DHCP, WINS, DNS и т. д.), ограничения — число портов и пропускная способность коммутаторов, маршрутизаторов и каналов связи, а также стоимость). 4.
* В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов. 5.
* В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой. 6.
* Представление графа в виде ярусно-параллельной формы или граф-схемы алгоритма в виде множества сечений (множества вершин в составе сечений могут быть неортогональными). 7.
* Разбиение графа алгоритма на непересекающиеся подграфы с последующим их размещением в процессорных элементах или элементах в составе ПЛИС при реализации конвейерной обработки данных (балансировка нагрузки).
rdf:langString
Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа у вигляді множини підмножин вершин за певними правилами. Зазвичай за умовою задачі потрібно, щоб , тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому . , більше 15-20 отриманих оптимальних розбиттях як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів. Необхідність отримання розбиття виникає при вирішенні ряду завдань: 1.
* Задача розфарбовування графа — кожна множина вершин складається з вершин одного кольору, причому вершини одного кольору не мають спільних інцидентних ребер. Зазвичай цікавить відшукання мінімальної розмальовки, що в загальному випадку є завданням класу NP (критерій оптимальності— ). 2.
* Завдання визначення числа і складу компонента зв'язності графа. 3.
* Під час проектування топології локальної мережі її розбиття на широкомовні домени визначається вимогами продуктивності (критерій оптимальності — обсяг переданого міждоменного трафіку при використанні різних серверів і мережевих служб (доступ до файлових серверів, служб DHCP, WINS, DNS і т. Д.), Обмеження — число портів і пропускна здатність комутаторів, маршрутизаторів і каналів зв'язку, а також вартість). 4.
* У задачі трасування з'єднань друкованих плат або мікросхем необхідно розбиття вихідної схеми на шари (кожен з яких представляє собою планарний граф). Критерії оптимальності — мінімальне число шарів і з'єднань (фактично, собівартість виробництва), обмеження — габаритні розміри і вимоги термічної і електромагнітної сумісності електронних компонентів. 5.
* У задачі розбиття граф-схеми алгоритму на блоки з метою реалізації на багатопроцесорної системі або логічному мультиконтроллером. Критерії оптимальності — мінімальне число блоків, мінімальні ступеня дублювання сигналів мікрооперацій і логічних умов, мінімальне число міжмодульних передач управління, мінімальний трафік міжмодульних передач управління і даних; обмеження диктуються використовуваною елементною базою. 6.
* Подання графа у вигляді ярусно-паралельної форми або граф-схеми алгоритму у вигляді безлічі перетинів (безлічі вершин у складі перетинів можуть бути неортогональної). 7.
* Розбиття графа алгоритму на непересічні підграфи з подальшим їх розміщенням в процесорних елементах або елементах в складі ПЛІС при реалізації конвеєрної обробки даних (балансування навантаження).
rdf:langString
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.
xsd:nonNegativeInteger
30274
