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.
| Attributes | Values |
|---|
| rdf:type
| |
| 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)
|
| 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)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has 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)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[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)
