HTML Microdata document

This HTML5 document contains 163 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dbpedia-de	http://de.dbpedia.org/resource/
dct	http://purl.org/dc/terms/
yago-res	http://yago-knowledge.org/resource/
n30	https://www.cs.princeton.edu/~bwk/btl.mirror/
dbo	http://dbpedia.org/ontology/
n16	http://dbpedia.org/resource/File:
foaf	http://xmlns.com/foaf/0.1/
dbpedia-ko	http://ko.dbpedia.org/resource/
n20	https://e-collection.library.ethz.ch/view/eth:
n18	https://global.dbpedia.org/id/
yago	http://dbpedia.org/class/yago/
dbpedia-ru	http://ru.dbpedia.org/resource/
dbt	http://dbpedia.org/resource/Template:
dbpedia-uk	http://uk.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
n26	http://masters.donntu.edu.ua/2006/fvti/krasnokutskaya/library/
freebase	http://rdf.freebase.com/ns/
dbpedia-sr	http://sr.dbpedia.org/resource/
dbpedia-pt	http://pt.dbpedia.org/resource/
n23	http://glaros.dtc.umn.edu/gkhome/node/
n11	http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fa	http://fa.dbpedia.org/resource/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
n28	http://cebichot.netne.net/graph_partitioning_book/
dbpedia-fr	http://fr.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbc	http://dbpedia.org/resource/Category:
dbp	http://dbpedia.org/property/
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/
n9	https://web.archive.org/web/20081003192033/http:/www.stanford.edu/~dgleich/demos/matlab/spectral/

Statements

Subject Item: dbr:Priority_matching
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Memetic_algorithm
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Bipartite_half
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Brian_Kernighan
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Algebraic_connectivity
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Approximate_max-flow_min-cut_theorem
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Arboricity
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:List_of_graph_theory_topics
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:DIMACS
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Vertex_separator
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:List_of_partition_topics
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Maximum_cut
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Network_theory
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Multipartite_graph
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:METIS
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Kernighan–Lin_algorithm
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:PLS_(complexity)
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Partition
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageDisambiguates: dbr:Graph_partition

Subject Item: dbr:Planar_separator_theorem
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Graph_partitioning
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: dbr:Minimum_cut
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Bregman–Minc_inequality
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Graph_(abstract_data_type)
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Graph_cuts_in_computer_vision
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Graph_partition
rdf:type: yago:Condition113920835 yago:Attribute100024264 yago:Problem114410605 yago:State100024720 yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Difficulty114408086 yago:WikicatComputationalProblemsInGraphTheory
rdfs:label: Partição de grafos Розбиття графа Graphpartitionierung 그래프 분할 Разбиение графа Graph partition Partitionnement de graphe
rdfs:comment: Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причём . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, 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 그래프 분할(graph partitioning) 문제는 수학에서 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이다. 이때 각 부분의 크기는 똑같아야 한다. 이 문제에는 다양한 변형이 있는데, 변마다 가중치를 주어서 가중치의 합이 가장 적게 되는 분할을 찾는 경우, 각 부분의 꼭짓점 수가 일정한 범위 안에서 차이나는 경우도 허용하는 경우 등이 있다. 그래프를 두 부분으로 나누는 문제를 특별히 그래프 이등분(graph bisection) 문제라고 한다. 그래프 분할 문제는 조합 최적화 문제 중에서 어려운 문제로, NP-완전에 속한다. 따라서 그래프 분할 문제의 최적해를 직접 구하기는 힘들고, 근사해를 구하기 위한 방법이 여럿 개발되어 있다. 대표적인 방법으로 과 FM 알고리즘이 있다. 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 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. Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа у вигляді множини підмножин вершин за певними правилами. Зазвичай за умовою задачі потрібно, щоб , тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому . , більше 15-20 отриманих оптимальних розбиттях як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів. 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.
foaf:depiction: n11:Graph_comparison.jpg n11:Bisected_network.jpg n11:Connected_graph..jpg
dct:subject: dbc:Computational_problems_in_graph_theory dbc:NP-complete_problems
dbo:wikiPageID: 11973947
dbo:wikiPageRevisionID: 1112459019
dbo:wikiPageWikiLink: dbc:Computational_problems_in_graph_theory dbc:NP-complete_problems dbr:Electronic_design_automation dbr:Adjacency_matrix dbr:P=NP dbr:Hypergraph dbr:Eigendecomposition dbr:METIS dbr:Graph_Laplacian dbr:Hamiltonian_mechanics n16:Bisected_network.jpg dbr:Spectral_clustering dbr:Minimum_cut dbr:Partition_of_a_set dbr:Preconditioning dbr:Degree_matrix dbr:VLSI dbr:Cheeger_bound dbr:Algebraic_connectivity dbr:Maximum_cut n16:Connected_graph..jpg dbr:LOBPCG dbr:Planar_separator_theorem dbr:Modularity_(networks) dbr:Laplacian_matrix dbr:Eigenvectors dbr:Finite_element_method n16:Graph_comparison.jpg dbr:ARPACK dbr:Fiduccia-Mattheyses_algorithm dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:NP-hard dbr:Kernighan–Lin_algorithm dbr:Multigrid dbr:Scikit-learn dbr:Planar_graph dbr:Conductance_(graph) dbr:Graph_partition
dbo:wikiPageExternalLink: n9:spectral.html n20:5739%3Fq=Balanced%20Partitioning%20of%20Grids%20and%20Related%20Graphs n23:107 n26:generals.pdf n28: n30:partitioning.pdf
owl:sameAs: dbpedia-pt:Partição_de_grafos dbpedia-uk:Розбиття_графа n18:4Ymyf wikidata:Q491370 dbpedia-fr:Partitionnement_de_graphe dbpedia-fa:افراز_گراف dbpedia-sr:Партиционисање_графа dbpedia-de:Graphpartitionierung freebase:m.02r_7wq yago-res:Graph_partition dbpedia-ru:Разбиение_графа dbpedia-ko:그래프_분할
dbp:wikiPageUsesTemplate: dbt:Dead_link dbt:Cite_conference dbt:Cite_book dbt:Short_description dbt:Harvtxt dbt:Radic dbt:Main dbt:Cite_journal
dbo:thumbnail: n11:Bisected_network.jpg?width=300
dbp:bot: InternetArchiveBot
dbp:date: January 2020
dbp:fixAttempted: yes
dbo:abstract: 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. Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа у вигляді множини підмножин вершин за певними правилами. Зазвичай за умовою задачі потрібно, щоб , тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому . , більше 15-20 отриманих оптимальних розбиттях як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів. Необхідність отримання розбиття виникає при вирішенні ряду завдань: 1. * Задача розфарбовування графа — кожна множина вершин складається з вершин одного кольору, причому вершини одного кольору не мають спільних інцидентних ребер. Зазвичай цікавить відшукання мінімальної розмальовки, що в загальному випадку є завданням класу NP (критерій оптимальності— ). 2. * Завдання визначення числа і складу компонента зв'язності графа. 3. * Під час проектування топології локальної мережі її розбиття на широкомовні домени визначається вимогами продуктивності (критерій оптимальності — обсяг переданого міждоменного трафіку при використанні різних серверів і мережевих служб (доступ до файлових серверів, служб DHCP, WINS, DNS і т. Д.), Обмеження — число портів і пропускна здатність комутаторів, маршрутизаторів і каналів зв'язку, а також вартість). 4. * У задачі трасування з'єднань друкованих плат або мікросхем необхідно розбиття вихідної схеми на шари (кожен з яких представляє собою планарний граф). Критерії оптимальності — мінімальне число шарів і з'єднань (фактично, собівартість виробництва), обмеження — габаритні розміри і вимоги термічної і електромагнітної сумісності електронних компонентів. 5. * У задачі розбиття граф-схеми алгоритму на блоки з метою реалізації на багатопроцесорної системі або логічному мультиконтроллером. Критерії оптимальності — мінімальне число блоків, мінімальні ступеня дублювання сигналів мікрооперацій і логічних умов, мінімальне число міжмодульних передач управління, мінімальний трафік міжмодульних передач управління і даних; обмеження диктуються використовуваною елементною базою. 6. * Подання графа у вигляді ярусно-паралельної форми або граф-схеми алгоритму у вигляді безлічі перетинів (безлічі вершин у складі перетинів можуть бути неортогональної). 7. * Розбиття графа алгоритму на непересічні підграфи з подальшим їх розміщенням в процесорних елементах або елементах в складі ПЛІС при реалізації конвеєрної обробки даних (балансування навантаження). Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причём . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), то есть оценка является завышенной. При значениях числа вершин графа более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется метод ветвей и границ), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов. Необходимость получения разбиения возникает при решении ряда задач: 1. * Задача раскраски графа — каждое множество вершин состоит из вершин одного цвета, причём вершины одного цвета не имеют общих инцидентных рёбер. Обычно интересует отыскание минимальной раскраски, что в общем случае является задачей класса NP (критерий оптимальности — ). 2. * Задача определения числа и состава компонент связности графа. 3. * При проектировании топологии локальной сети её разбиение на широковещательные домены определяется требованиями производительности (критерий оптимальности — объем передаваемого междоменного трафика при использовании различных серверов и сетевых служб (доступ к файловым серверам, службам DHCP, WINS, DNS и т. д.), ограничения — число портов и пропускная способность коммутаторов, маршрутизаторов и каналов связи, а также стоимость). 4. * В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов. 5. * В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой. 6. * Представление графа в виде ярусно-параллельной формы или граф-схемы алгоритма в виде множества сечений (множества вершин в составе сечений могут быть неортогональными). 7. * Разбиение графа алгоритма на непересекающиеся подграфы с последующим их размещением в процессорных элементах или элементах в составе ПЛИС при реализации конвейерной обработки данных (балансировка нагрузки). 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 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. 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. 그래프 분할(graph partitioning) 문제는 수학에서 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이다. 이때 각 부분의 크기는 똑같아야 한다. 이 문제에는 다양한 변형이 있는데, 변마다 가중치를 주어서 가중치의 합이 가장 적게 되는 분할을 찾는 경우, 각 부분의 꼭짓점 수가 일정한 범위 안에서 차이나는 경우도 허용하는 경우 등이 있다. 그래프를 두 부분으로 나누는 문제를 특별히 그래프 이등분(graph bisection) 문제라고 한다. 그래프 분할 문제는 조합 최적화 문제 중에서 어려운 문제로, NP-완전에 속한다. 따라서 그래프 분할 문제의 최적해를 직접 구하기는 힘들고, 근사해를 구하기 위한 방법이 여럿 개발되어 있다. 대표적인 방법으로 과 FM 알고리즘이 있다.
prov:wasDerivedFrom: wikipedia-en:Graph_partition?oldid=1112459019&ns=0
dbo:wikiPageLength: 30274
foaf:isPrimaryTopicOf: wikipedia-en:Graph_partition

Subject Item: dbr:List_of_NP-complete_problems
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Hyperbolic_geometric_graph
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Hypergraph
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Uniquely_colorable_graph
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Multi-level_technique
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: dbr:Modular_decomposition
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Split_graph
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Fiduccia–Mattheyses_algorithm
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Graph_bisection
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: dbr:Graph_bisection_problem
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: dbr:Graph_partitioning_problem
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: dbr:Rainbow-independent_set
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Scotch
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Extremal_Ensemble_Learning
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:NP-intermediate
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Strength_of_a_graph
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Streamline_upwind_Petrov–Galerkin_pressure-stabilizing_Petrov–Galerkin_formulation_for_incompressible_Navier–Stokes_equations
dbo:wikiPageWikiLink: dbr:Graph_partition

Subject Item: dbr:Mutli_level_technique
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: dbr:Partition_of_a_graph
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: dbr:Multi_level_technique
dbo:wikiPageWikiLink: dbr:Graph_partition
dbo:wikiPageRedirects: dbr:Graph_partition

Subject Item: wikipedia-en:Graph_partition
foaf:primaryTopic: dbr:Graph_partition