Bipartite graph
http://dbpedia.org/resource/Bipartite_graph an entity of type: Abstraction100002137
Pojmem bipartitní graf nebo sudý graf se v teorii grafů označuje takový graf, jehož množinu vrcholů je možné rozdělit na dvě disjunktní množiny tak, že žádné dva vrcholy ze stejné množiny nejsou spojeny hranou.
rdf:langString
Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.
rdf:langString
En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire.
rdf:langString
数学、とくにグラフ理論における2部グラフ（にぶグラフ、英: bipartite graph）とは、頂点集合を2つに分割して各部分の頂点は互いに隣接しないようにできるグラフのことである。一般に互いに隣接しない頂点からなる集合を独立集合といい、頂点集合を n 個の独立集合に分割可能なグラフのことを n 部グラフ (n-partite graph) という。 頂点集合を独立集合 V1, V2 に分割したとき、V1 と V2 の任意の頂点が隣接するグラフを完全2部グラフという。頂点集合が m 頂点とn 頂点に分割される完全2部グラフを Km, n と書く。 辺を共有する頂点を異なる色で塗ることを（頂点）彩色という。よって、n 部グラフは n 彩色可能なグラフに他ならない。同様に、頂点を共有する辺を異なる色で塗ることを辺彩色という。 2部グラフの辺集合はどの2辺も互いに隣接していないときマッチングと呼ばれる。辺の数が最大のマッチングを最大マッチングと呼ぶ。また、すべての頂点がマッチングに含まれる辺の端点であるとき完全マッチングと呼ぶ。
rdf:langString
그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.
rdf:langString
Graf dwudzielny – graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru. Równoważnie: graf, który nie zawiera cykli nieparzystej długości. Jeśli pomiędzy wszystkimi parami wierzchołków należących do różnych zbiorów istnieje krawędź, graf taki nazywamy pełnym grafem dwudzielnym lub kliką dwudzielną i oznaczamy gdzie i oznaczają liczności zbiorów wierzchołków. Pojęcie można uogólnić na trzy i więcej zbiorów.
rdf:langString
Nella teoria dei grafi, un grafo bipartito è un grafo tale che l'insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice di una di queste due parti è collegato solo a vertici dell'altra. Più formalmente, consideriamo un grafo non orientato ; esso si dice grafo bipartito se il suo insieme dei vertici può essere bipartito in due sottoinsiemi disgiunti tali che ogni arco in ha la forma con e . Un grafo bipartito può essere efficacemente presentato con una notazione della forma .
rdf:langString
En bipartit graf, även kallad tvådelad graf, är en graf vars hörnmängd kan partitioneras som där och där varje kant kan skrivas på formen , där och . I så fall säges ha bipartitionen (X,Y). Detta kan även uttryckas så att noderna i en bipartit graf kan indelas i två mängder, sådana att inga kanter går mellan två noder i samma mängd.
rdf:langString
У математиці двочастковий граф (також біграф, двочастинний або дводольний граф) — граф, множину вершин якого можна розбити на дві підмножини так, що кожне ребро графа має одну вершину з першої підмножини і одну з другої.
rdf:langString
在圖論中，二部圖是一類特殊的圖，又稱為二部图、偶图、雙分圖。二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖，使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的，二分圖可以被定義成圖中所有的環都有偶數個頂點。 可以将 和 当做一個着色： 中所有頂點为蓝色， 中所有頂點着绿色，每条边的两个端点的颜色不同，符合图着色问题的要求。相反的，非二分圖無法被二著色，例如 (3 個頂點的完全圖)，將其中一个顶点着蓝色并且另外一个着绿色后，第三个顶点与上述具有两个颜色的顶点相连，无法再对它着蓝色或绿色。 二分图的一种描述方式为：，包含了独立集 和 ，以及边 的資訊。假如不是连通图，可能有多種將所有頂點分成 和 的方式；在特定的應用場合中，將頂點的兩部分、寫出來是有必要的。如果，則 称为平衡二分图。如果二分图 以及 的顶点分別有相同的度數，則 被稱為是。 给定一个二分图 ，在 的一个子图 中， 的边集中的任意两条边都沒有共同的端点，则称 是一个匹配。
rdf:langString
Двудо́льный граф или бигра́ф в теории графов — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части, то есть не существует рёбер между вершинами одной и той же части графа.
rdf:langString
في نظرية المخططات في الرياضيات، يكون المخطط أو ثنائي التجزئة (بالإنجليزية: Bipartite Graph) إذا أمكن تقسيم رؤوسه إلى مجموعتين و حيث يكون أحد رؤوس أي ضلع في والرأس الآخر في . مجموعات الرؤوس و عادة تسمى اجزاء الرسم. إذا كان والذي يعني مجموعتين جزئيتين لهما نفس عدد العناصر (cardinality) فإن تسمى المخطط المتوازن ثنائي التجزئة (balanced bipartite graph). إذا كانت جميع الرؤوس في جانب معين من التجزئة لها نفس الدرجة، فإن تسمى ثنائي منتظم (biregular).
rdf:langString
Un graf bipartit és en teoria de grafs un graf no dirigit els vèrtexs del qual es poden separar en dos conjunts disjunts i i les arestes sempre uneixen vèrtexs d'un conjunt amb vèrtexs d'un altre: * * * no hi ha cap aresta ni Sent el conjunt que conté tots els vèrtexs del graf. Els grafs bipartits solen representar gràficament amb dues columnes (o files) de vèrtexs i les arestes unint vèrtexs de columnes (o files) diferents.
rdf:langString
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
rdf:langString
En grafeteorio, dukolora grafeo (aŭ duparta grafeo) estas grafeo kies verticojn oni povas dividi en du disajn arojn kaj , en kiu ĉiu eĝo ligas verticon en al vertico en . Verticaro kaj ofte nomiĝas la partoj de la grafeo. Ekvivalente, dukolora grafeo estas grafeo sen nepara ciklo. La du partojn , oni povas pripensi kiel kolorado de la grafeo per du koloroj: ekzemple verticoj en estu bluaj, kaj verticoj en verdaj. Do la randoj de ĉiu eĝo havas malsamajn kolorojn. Kontraste, ĉi tia kolorado ne eblas en ne-dukolora grafeo, ekzemple unu triangulo.
rdf:langString
En teoría de grafos, un grafo bipartito es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos, de manera que las aristas no pueden relacionar vértices de un mismo conjunto. Un grafo bipartito completo es un grafo bipartito en que todos los vértices de uno de los subconjuntos están relacionados con los del otro subconjunto.
rdf:langString
No campo da matemática da teoria dos grafos, um grafo bipartido ou bigrafo é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V; ou seja, U e V são conjuntos independentes. Equivalentemente, um grafo bipartido é um grafo que não contém qualquer ciclo de comprimento ímpar. Frequentemente se escreve G = (U, V, E) para denotar um grafo bipartido cuja partição tem as partes U e V. Se |U| =|V|, ou seja, se os dois subconjuntos tem igual cardinalidade, então G é chamado um grafo bipartido balanceado.
rdf:langString
rdf:langString
مخطط ثنائي
rdf:langString
Graf bipartit
rdf:langString
Bipartitní graf
rdf:langString
Bipartiter Graph
rdf:langString
Dukolora grafeo
rdf:langString
Bipartite graph
rdf:langString
Grafo bipartito
rdf:langString
Graphe biparti
rdf:langString
Grafo bipartito
rdf:langString
2部グラフ
rdf:langString
이분 그래프
rdf:langString
Graf dwudzielny
rdf:langString
Grafo bipartido
rdf:langString
Bipartit graf
rdf:langString
Двудольный граф
rdf:langString
二分图
rdf:langString
Двочастковий граф
xsd:integer
244431
xsd:integer
1123220626
rdf:langString
right
rdf:langString
Example of a bipartite graph without cycles
rdf:langString
p/g044880
rdf:langString
Simple bipartite graph; no crossings.svg
rdf:langString
Simple bipartite graph; two layers.svg
xsd:integer
1
rdf:langString
Bipartite Graph
rdf:langString
Graph, bipartite
xsd:integer
230
rdf:langString
BipartiteGraph
rdf:langString
cs2
rdf:langString
في نظرية المخططات في الرياضيات، يكون المخطط أو ثنائي التجزئة (بالإنجليزية: Bipartite Graph) إذا أمكن تقسيم رؤوسه إلى مجموعتين و حيث يكون أحد رؤوس أي ضلع في والرأس الآخر في . مجموعات الرؤوس و عادة تسمى اجزاء الرسم. بصيغه أخرى، الرسم ثنائي التجزئة هو الرسم الذي لايحتوي على أي دارات فرديه. أي مجموعتين و ممكن ان تلون بلونين حسب تلوين المخططات عن طريق تلوين رؤوس الجزء بالأزرق مثلا وجميع رؤوس الجزء باللون الأخضر. بالتالي كل ضلع له طرفين بلونين مختلفين وهو المطلوب في مسألة تلوين المخططات. بالمقابل، من المستحيل تلوين أي نوع اخر من المخططات الغير ثنائية التجزئة بلونين فقط. مثال على ذلك تلوين رؤوس المثلث، والتي يمكن تلوين أحد الرؤوس بالأزرق ورأس اخر بالاخضر لكن الراس الثالث مرتبط بالرأسين الازرق والاخضر مما يستحيل تلوينه بأحد هذين اللونين.بالعادة الرمز يرمز لمخطط ثنائي التجزئة والذي له التجزئة و في حين المجموعة ترمز لمجموعة اضلاع الرسم. إذا كان المخطط ثنائي التجزئة غير مترابط، فمن الممكن أن يكون له أكثر من تجزئة. في هذه الحالة الرمز مفيد لتوضيح تجزئة معينه والتي ممكن ان تكون مهمه في تطبيق ما. إذا كان والذي يعني مجموعتين جزئيتين لهما نفس عدد العناصر (cardinality) فإن تسمى المخطط المتوازن ثنائي التجزئة (balanced bipartite graph). إذا كانت جميع الرؤوس في جانب معين من التجزئة لها نفس الدرجة، فإن تسمى ثنائي منتظم (biregular).
rdf:langString
Un graf bipartit és en teoria de grafs un graf no dirigit els vèrtexs del qual es poden separar en dos conjunts disjunts i i les arestes sempre uneixen vèrtexs d'un conjunt amb vèrtexs d'un altre: * * * no hi ha cap aresta ni Sent el conjunt que conté tots els vèrtexs del graf. Els grafs bipartits solen representar gràficament amb dues columnes (o files) de vèrtexs i les arestes unint vèrtexs de columnes (o files) diferents. Els dos conjunts U i V poden ser pensats com un acolorit del graf amb dos colors: si vam pintar els vèrtexs de U de blau i els vèrtexs de V de verd obtenim un graf de dos colors on cada aresta té un vèrtex blau i l'altre verd. D'altra banda, si un gràfic no té la propietat que es pot pintar amb dos colors no és bipartit. Un graf bipartit sol amb la partició dels vèrtexs en U i V sol denotar G = ( U, V, L ). Si |U|=|V|, és a dir, si els dos subconjunts té la mateixa quantitat d'elements, diem que el graf bipartit G és balancejat.
rdf:langString
Pojmem bipartitní graf nebo sudý graf se v teorii grafů označuje takový graf, jehož množinu vrcholů je možné rozdělit na dvě disjunktní množiny tak, že žádné dva vrcholy ze stejné množiny nejsou spojeny hranou.
rdf:langString
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes to denote a bipartite graph whose partition has the parts and , with denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition; in this case, the notation is helpful in specifying one particular bipartition that may be of importance in an application. If , that is, if the two subsets have equal cardinality, then is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then is called biregular.
rdf:langString
En grafeteorio, dukolora grafeo (aŭ duparta grafeo) estas grafeo kies verticojn oni povas dividi en du disajn arojn kaj , en kiu ĉiu eĝo ligas verticon en al vertico en . Verticaro kaj ofte nomiĝas la partoj de la grafeo. Ekvivalente, dukolora grafeo estas grafeo sen nepara ciklo. La du partojn , oni povas pripensi kiel kolorado de la grafeo per du koloroj: ekzemple verticoj en estu bluaj, kaj verticoj en verdaj. Do la randoj de ĉiu eĝo havas malsamajn kolorojn. Kontraste, ĉi tia kolorado ne eblas en ne-dukolora grafeo, ekzemple unu triangulo. Oni ofte skribas por signifi dukolora grafeo kun partoj kun , kaj signas la eĝaro. Se dukolora grafeo ne estas konekteca, ĝi eble havas plurajn dukoloradojn; tiel, povas signi unu el la dukoloradoj utila por la nuna problemo. Se , t.e. la du partoj enhavas same da elementoj, nomiĝas ekvilibra dukolora grafeo. Se ĉiuj verticoj en ambaŭ partoj havas saman gradon, nomiĝas .
rdf:langString
Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.
rdf:langString
En teoría de grafos, un grafo bipartito es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos, de manera que las aristas no pueden relacionar vértices de un mismo conjunto. Un grafo bipartito completo es un grafo bipartito en que todos los vértices de uno de los subconjuntos están relacionados con los del otro subconjunto. Este concepto se puede generalizar al de grafo s-partito, como un grafo cuyo conjunto de vértices se puede particionar en s subconjuntos, de modo que las aristas solo conectan a vértices de subconjuntos diferentes. Análogamente, también se puede definir un grafo s-bipartito completo, como uno en que todos los pares de vértices pertenecientes a subconjuntos diferentes son adyacentes.
rdf:langString
En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire.
rdf:langString
数学、とくにグラフ理論における2部グラフ（にぶグラフ、英: bipartite graph）とは、頂点集合を2つに分割して各部分の頂点は互いに隣接しないようにできるグラフのことである。一般に互いに隣接しない頂点からなる集合を独立集合といい、頂点集合を n 個の独立集合に分割可能なグラフのことを n 部グラフ (n-partite graph) という。 頂点集合を独立集合 V1, V2 に分割したとき、V1 と V2 の任意の頂点が隣接するグラフを完全2部グラフという。頂点集合が m 頂点とn 頂点に分割される完全2部グラフを Km, n と書く。 辺を共有する頂点を異なる色で塗ることを（頂点）彩色という。よって、n 部グラフは n 彩色可能なグラフに他ならない。同様に、頂点を共有する辺を異なる色で塗ることを辺彩色という。 2部グラフの辺集合はどの2辺も互いに隣接していないときマッチングと呼ばれる。辺の数が最大のマッチングを最大マッチングと呼ぶ。また、すべての頂点がマッチングに含まれる辺の端点であるとき完全マッチングと呼ぶ。
rdf:langString
그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.
rdf:langString
Graf dwudzielny – graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru. Równoważnie: graf, który nie zawiera cykli nieparzystej długości. Jeśli pomiędzy wszystkimi parami wierzchołków należących do różnych zbiorów istnieje krawędź, graf taki nazywamy pełnym grafem dwudzielnym lub kliką dwudzielną i oznaczamy gdzie i oznaczają liczności zbiorów wierzchołków. Pojęcie można uogólnić na trzy i więcej zbiorów.
rdf:langString
Nella teoria dei grafi, un grafo bipartito è un grafo tale che l'insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice di una di queste due parti è collegato solo a vertici dell'altra. Più formalmente, consideriamo un grafo non orientato ; esso si dice grafo bipartito se il suo insieme dei vertici può essere bipartito in due sottoinsiemi disgiunti tali che ogni arco in ha la forma con e . Un grafo bipartito può essere efficacemente presentato con una notazione della forma .
rdf:langString
No campo da matemática da teoria dos grafos, um grafo bipartido ou bigrafo é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V; ou seja, U e V são conjuntos independentes. Equivalentemente, um grafo bipartido é um grafo que não contém qualquer ciclo de comprimento ímpar. Os dois conjuntos U e V podem ser pensados como uma coloração do grafo com duas cores: se nós colorirmos todos os nodos em U de azul, e todos os nodos em V de verde, cada aresta tem terminações de cores diferentes, como é exigido no problema de coloração de grafos. Em contrapartida, tal coloração é impossível no caso de um grafo que não é bipartido, como um : depois de um nó ser colorido de cor azul e outro de verde, o terceiro vértice do triângulo é ligado a vértices de ambas as cores, impedindo que seja atribuída qualquer cor. Frequentemente se escreve G = (U, V, E) para denotar um grafo bipartido cuja partição tem as partes U e V. Se |U| =|V|, ou seja, se os dois subconjuntos tem igual cardinalidade, então G é chamado um grafo bipartido balanceado.
rdf:langString
En bipartit graf, även kallad tvådelad graf, är en graf vars hörnmängd kan partitioneras som där och där varje kant kan skrivas på formen , där och . I så fall säges ha bipartitionen (X,Y). Detta kan även uttryckas så att noderna i en bipartit graf kan indelas i två mängder, sådana att inga kanter går mellan två noder i samma mängd.
rdf:langString
У математиці двочастковий граф (також біграф, двочастинний або дводольний граф) — граф, множину вершин якого можна розбити на дві підмножини так, що кожне ребро графа має одну вершину з першої підмножини і одну з другої.
rdf:langString
在圖論中，二部圖是一類特殊的圖，又稱為二部图、偶图、雙分圖。二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖，使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的，二分圖可以被定義成圖中所有的環都有偶數個頂點。 可以将 和 当做一個着色： 中所有頂點为蓝色， 中所有頂點着绿色，每条边的两个端点的颜色不同，符合图着色问题的要求。相反的，非二分圖無法被二著色，例如 (3 個頂點的完全圖)，將其中一个顶点着蓝色并且另外一个着绿色后，第三个顶点与上述具有两个颜色的顶点相连，无法再对它着蓝色或绿色。 二分图的一种描述方式为：，包含了独立集 和 ，以及边 的資訊。假如不是连通图，可能有多種將所有頂點分成 和 的方式；在特定的應用場合中，將頂點的兩部分、寫出來是有必要的。如果，則 称为平衡二分图。如果二分图 以及 的顶点分別有相同的度數，則 被稱為是。 给定一个二分图 ，在 的一个子图 中， 的边集中的任意两条边都沒有共同的端点，则称 是一个匹配。
rdf:langString
Двудо́льный граф или бигра́ф в теории графов — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части, то есть не существует рёбер между вершинами одной и той же части графа.
xsd:nonNegativeInteger
33009
