Cut (graph theory) (original) (raw)
Ein Schnitt bezeichnet in der Graphentheorie eine Partition der Knotenmenge eines Graphen.Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit Netzwerken zu. Schnitte können aber auch unabhängig von Netzwerken definiert und untersucht werden.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de grafs, un tall és una partició dels vèrtexs d'un graf en dos subconjunts disjunts. El conjunt de tall és el conjunt d'arestes que enllacen vèrtexs que estan en diferents subconjunts de la partició. Es diu que les arestes travessen el tall quan estan dins el conjunt de tall. En un graf no dirigit i no , la mida o pes del tall és el nombre d'arestes que aquest travessa. En un graf ponderat, és la suma dels pesos de les arestes que són tallades. En una xarxa de flux, un tall s-t és un tall en què la font i el pou estan en diferents subconjunts, i el conjunt de tall sols està compost per arestes que van des del costat de la font fins al costat del pou. La capacitat d'un tall s-t és definida per la suma de les capacitats de les arestes del conjunt de tall. El tall d'un graf també pot referir-se al mateix conjunt de tall. (ca) In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions. In a flow network, an s–t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side. The capacity of an s–t cut is defined as the sum of the capacity of each edge in the cut-set. (en) Ein Schnitt bezeichnet in der Graphentheorie eine Partition der Knotenmenge eines Graphen.Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit Netzwerken zu. Schnitte können aber auch unabhängig von Netzwerken definiert und untersucht werden. (de) En théorie des graphes, une coupe d'un graphe est une partition des sommets en deux sous-ensembles. On appelle aussi coupe l'ensemble des arêtes ayant une extrémité dans chaque sous-ensemble de la partition. Si les arêtes ont un poids, le poids de la coupe est la somme des poids respectifs des arêtes de la coupe. Sinon, c'est le nombre d'arêtes dans la coupe. Cet objet apparaît dans la modélisation de nombreux problèmes concernant les réseaux, où l'on recherche une coupe s-t, c'est-à-dire une coupe séparant deux sommets s et t spécifiés. (fr) グラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。このとき、ある辺 (u,v) E の端点が u S かつ v T（有向グラフの場合 u T でかつ v S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。 カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワークでは、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される（逆方向のエッジは加算されない）。 頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、劣モジュラ関数、かつ、である。 (ja) Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti. Ogni taglio determina un insieme di taglio (o cut-set), definito come l'insieme degli archi che hanno i propri estremi nei due sottinsiemi della partizione. In un grafo connesso, ogni cut-set è relativo ad un unico taglio. In una rete di flusso, un taglio s-t è un taglio tale che il vertice sorgente (s) ed il pozzo (t) non appartengano allo stesso sottinsieme della partizione. La capacità di un taglio s-t è definita come la somma delle capacità degli archi appartenenti al cut-set. (it) Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что 1. * , где — множество вершин графа 2. * 3. * , где — исток, — сток. Величиной разреза называется сумма пропускных способностей таких рёбер , что . (ru) Введемо розбиття вершин графа на дві неперетинні множини, тоді розріз графа складає множина дуг, які з’єднують утворені підмножини вершин. В потоковій мережі, s-t розріз це розріз, в якому джерело (англ. source) і стік (англ. sink), вершини з нульовими напівстепенями входу і виходу відповідно, знаходяться в різних підмножинах вершин, та містить лише дуги, що ведуть від джерела до стоку. Сума пропускних здатностей усіх дуг розрізу називається величиною розрізу (його пропускною здатністю). Також розрізом графа можуть називати дві утворені множини вершин. (uk) Ett snitt är en uppdelning av alla noder i en graf i två disjunkta delmängder. Mängden av bågar som går mellan de två delmängderna kallas skurna bågar. I en graf utan vikter på bågarna är snittets värde antalet skurna bågar. I en viktad graf är värdet summan av alla skurna bågars vikter. (sv) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Min-cut.svg?width=300 |
| dbo:wikiPageID | 2180494 (xsd:integer) |
| dbo:wikiPageLength | 9648 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097329463 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Basis_(linear_algebra) dbc:Graph_connectivity dbr:Cycle_space dbr:Vector_space dbr:Vertex_separator dbc:Combinatorial_optimization dbr:Connected_graph dbr:Connectivity_(graph_theory) dbr:Max-flow_min-cut_theorem dbr:Glossary_of_graph_theory dbr:Gomory–Hu_tree dbr:Graph_(discrete_mathematics) dbr:Objective_function dbr:Split_(graph_theory) dbr:Tree_(graph_theory) dbr:Karp's_21_NP-complete_problems dbr:Linear_programming dbr:Cycle_graph dbr:Finite_field dbr:Flow_network dbr:Bridge_(graph_theory) dbr:Partition_of_a_set dbr:Edmonds–Karp_algorithm dbr:Graph_cuts_in_computer_vision dbr:Graph_theory dbr:Bipartite_graph dbr:Polynomial_time dbr:Approximation_ratio dbr:Orthogonal_complement dbr:Vertex_(graph_theory) dbr:Symmetric_difference dbr:Semidefinite_programming dbr:Disjoint_set dbr:Constant-factor_approximation_algorithm dbr:File:Max-cut.svg dbr:File:Min-cut.svg |
| dbp:wikiPageUsesTemplate | dbt:! dbt:Harvtxt dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_connectivity dbc:Combinatorial_optimization |
| gold:hypernym | dbr:Partition |
| rdf:type | dbo:AnatomicalStructure yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| rdfs:comment | Ein Schnitt bezeichnet in der Graphentheorie eine Partition der Knotenmenge eines Graphen.Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit Netzwerken zu. Schnitte können aber auch unabhängig von Netzwerken definiert und untersucht werden. (de) En théorie des graphes, une coupe d'un graphe est une partition des sommets en deux sous-ensembles. On appelle aussi coupe l'ensemble des arêtes ayant une extrémité dans chaque sous-ensemble de la partition. Si les arêtes ont un poids, le poids de la coupe est la somme des poids respectifs des arêtes de la coupe. Sinon, c'est le nombre d'arêtes dans la coupe. Cet objet apparaît dans la modélisation de nombreux problèmes concernant les réseaux, où l'on recherche une coupe s-t, c'est-à-dire une coupe séparant deux sommets s et t spécifiés. (fr) グラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。このとき、ある辺 (u,v) E の端点が u S かつ v T（有向グラフの場合 u T でかつ v S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。 カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワークでは、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される（逆方向のエッジは加算されない）。 頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、劣モジュラ関数、かつ、である。 (ja) Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti. Ogni taglio determina un insieme di taglio (o cut-set), definito come l'insieme degli archi che hanno i propri estremi nei due sottinsiemi della partizione. In un grafo connesso, ogni cut-set è relativo ad un unico taglio. In una rete di flusso, un taglio s-t è un taglio tale che il vertice sorgente (s) ed il pozzo (t) non appartengano allo stesso sottinsieme della partizione. La capacità di un taglio s-t è definita come la somma delle capacità degli archi appartenenti al cut-set. (it) Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что 1. * , где — множество вершин графа 2. * 3. * , где — исток, — сток. Величиной разреза называется сумма пропускных способностей таких рёбер , что . (ru) Введемо розбиття вершин графа на дві неперетинні множини, тоді розріз графа складає множина дуг, які з’єднують утворені підмножини вершин. В потоковій мережі, s-t розріз це розріз, в якому джерело (англ. source) і стік (англ. sink), вершини з нульовими напівстепенями входу і виходу відповідно, знаходяться в різних підмножинах вершин, та містить лише дуги, що ведуть від джерела до стоку. Сума пропускних здатностей усіх дуг розрізу називається величиною розрізу (його пропускною здатністю). Також розрізом графа можуть називати дві утворені множини вершин. (uk) Ett snitt är en uppdelning av alla noder i en graf i två disjunkta delmängder. Mängden av bågar som går mellan de två delmängderna kallas skurna bågar. I en graf utan vikter på bågarna är snittets värde antalet skurna bågar. I en viktad graf är värdet summan av alla skurna bågars vikter. (sv) En teoria de grafs, un tall és una partició dels vèrtexs d'un graf en dos subconjunts disjunts. El conjunt de tall és el conjunt d'arestes que enllacen vèrtexs que estan en diferents subconjunts de la partició. Es diu que les arestes travessen el tall quan estan dins el conjunt de tall. En un graf no dirigit i no , la mida o pes del tall és el nombre d'arestes que aquest travessa. En un graf ponderat, és la suma dels pesos de les arestes que són tallades. El tall d'un graf també pot referir-se al mateix conjunt de tall. (ca) In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions. (en) |
| rdfs:label | Tall (graf) (ca) Schnitt (Graphentheorie) (de) Cut (graph theory) (en) Coupe (théorie des graphes) (fr) Taglio (teoria dei grafi) (it) カット (グラフ理論) (ja) Разрез (теория графов) (ru) Розріз (теорія графів) (uk) Snitt (grafteori) (sv) |
| owl:sameAs | freebase:Cut (graph theory) yago-res:Cut (graph theory) wikidata:Cut (graph theory) dbpedia-ca:Cut (graph theory) dbpedia-de:Cut (graph theory) dbpedia-fa:Cut (graph theory) dbpedia-fr:Cut (graph theory) dbpedia-it:Cut (graph theory) dbpedia-ja:Cut (graph theory) dbpedia-ru:Cut (graph theory) dbpedia-sv:Cut (graph theory) dbpedia-uk:Cut (graph theory) dbpedia-vi:Cut (graph theory) https://global.dbpedia.org/id/bQmw |
| prov:wasDerivedFrom | wikipedia-en:Cut_(graph_theory)?oldid=1097329463&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Max-cut.svg wiki-commons:Special:FilePath/Min-cut.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Cut_(graph_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Cut |
| is dbo:wikiPageRedirects of | dbr:Cut_space dbr:Graph-cut dbr:S-t_cut dbr:Size_of_the_cut dbr:Minimum_vertex_cut dbr:Cut_set dbr:Cutset dbr:Sparsest_Cut dbr:Sparsest_cut dbr:Sparsest_cut_problem |
| is dbo:wikiPageWikiLink of | dbr:Enumeration_algorithm dbr:Betweenness_centrality dbr:Cycle_basis dbr:Cycle_space dbr:Conductance_(graph) dbr:Connectivity_(graph_theory) dbr:Maximum_cut dbr:Maximum_flow_problem dbr:Quadratically_constrained_quadratic_program dbr:Glossary_of_graph_theory dbr:Gomory–Hu_tree dbr:Connectomics dbr:Planar_separator_theorem dbr:Split_(graph_theory) dbr:Steinitz's_theorem dbr:Cederbaum's_maximum_flow_theorem dbr:Cut dbr:K-edge-connected_graph dbr:Karger's_algorithm dbr:Laplacian_matrix dbr:Linear_network_coding dbr:Minimum_cut dbr:Cut_space dbr:Dual_graph dbr:Flow_network dbr:Bridge_(graph_theory) dbr:Graph_cut_optimization dbr:Graph_cuts_in_computer_vision dbr:Graph_cut dbr:2-satisfiability dbr:Courcelle's_theorem dbr:Bipartite_graph dbr:Graph-cut dbr:Minimum_spanning_tree dbr:Randomized_algorithm dbr:Seam_carving dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:∂ dbr:Property_testing dbr:Stoer–Wagner_algorithm dbr:S-t_cut dbr:Size_of_the_cut dbr:Minimum_vertex_cut dbr:Cut_set dbr:Cutset dbr:Sparsest_Cut dbr:Sparsest_cut dbr:Sparsest_cut_problem |
| is foaf:primaryTopic of | wikipedia-en:Cut_(graph_theory) |
