| dbo:abstract
|
- للمقارنة بين رسمين بيانيين، انظر مطابقة الرسوم البيانية. في الانضباط الرياضي لنظرية الرسم البياني، تكون الحافة المطابقة أو المستقلة المحددة في الرسم البياني عبارة عن مجموعة من الحواف بدون رؤوس شائعة. في بعض التطابقات، قد تكون جميع الرؤوس حادثة مع بعض حافة المطابقة، ولكن هذا ليس مطلوبًا ولا يمكن أن يحدث إلا إذا كان عدد الرؤوس حتى. يمكن العثور على العثور على مطابقة في ثنائي المسار كمشكلة تدفق الشبكة (ar)
- En la disciplina matemàtica de la teoria de grafs, un aparellament d'un graf és un conjunt d'arestes sense vèrtexs en comú. També pot ser un graf complet que consisteixi d'arestes sense vèrtexs comuns. L'aparellament bipartit és un cas especial d'un problema sobre una xarxa de flux. (ca)
- Párování grafu je v teorii grafů taková podmnožina hran grafu, že žádné dvě hrany z této množiny nemají společný vrchol. Idea je taková, že vrcholy grafů dáváme do párů. Pár může vzniknout jen tam, kde byla hrana. Přitom každý vrchol může být jen v jednom páru. Řadu praktických problémů lze převést na algoritmizované hledání jistého typu párování v grafu. (cs)
- Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird. Folgende Situation wird dabei betrachtet: Gegeben sei eine Menge von Dingen und zu diesen Dingen Informationen darüber, welche davon einander zugeordnet werden könnten. Ein Matching (in der Literatur manchmal auch Paarung) ist dann als eine solche Auswahl aus den möglichen Zuordnungen definiert, die kein Ding mehr als einmal zuordnet. Die am häufigsten gestellten Fragen in dieser Situation sind dann die folgenden: 1.
* Wie findet man ein Matching, das eine maximale Anzahl an Dingen einander zuordnet?Dieses Problem ist das klassische Matchingproblem. 2.
* Gibt es ein Matching, das alle Dinge zuordnet? Wenn ja, wie viele?Solche Matchings heißen perfektes Matching. Die Anzahl der perfekten Matchings in einem Graphen wird meistens mit notiert. 3.
* Angenommen, man könnte quantifizieren „wie wichtig“ (oder „teuer“) die einzelnen Zuordnungen wären: Wie findet man dann ein Matching, das eine maximale Zahl von Dingen zuordnet und dabei ein möglichst großes (oder kleines) Gewicht hat?Dieses Problem heißt gewichtetes Matchingproblem. Zwischen einer Maximierungs- und einer Minimierungsaufgabe wird hier oftmals nicht unterschieden: Indem man bei allen Gewichten (Kosten) das Vorzeichen vertauscht, kann man beide Probleme ohne nennenswerten Aufwand ineinander überführen. 4.
* Angenommen, man hätte genau zwei Klassen von Dingen und angenommen, man wüsste, dass es ausschließlich zwischen diesen Klassen mögliche Zuordnungen gibt. Werden die Probleme 1–3 dadurch einfacher?Dieses Problem heißt bipartites (gewichtetes) Matchingproblem und ist ein viel diskutierter Spezialfall. 5.
* Kann man anderes Wissen, das man über die Struktur der möglichen Zuordnungen hat, ähnlich wie in 4 geschickt benutzen, um die Probleme 1–3 effizienter zu lösen? Die Theorie um die Matchings untersucht möglichst effiziente Lösungsverfahren dieser Probleme, klassifiziert diese nach ihrer Laufzeit mit den Methoden der Komplexitätstheorie und stellt Beziehungen dieser Probleme zueinander und zu anderen Problemen in der Mathematik her. (de)
- Grafo bateko parekatzea erpin edo puntu komunik ez duten ertzen multzo bat da, elkarren ondokoak ez diren ertzen multzo bat alegia. Erpin bat parekatua dela esaten da parekatzearen ertz baten mutur batean badago. Bestela parekatu gabe dagoela esaten da. Parekatze maximoa ahalik eta ertz kopuru handiena biltzen duen parekatzea da. Grafo batean parekatze maximo bat baino gehiago izan daiteke. Honako irudian parekatze maximo bana azaltzen da hiru grafotarako: Parekatze maximala, bere barnean ez dagoen ertz bat gaineratzen bada, parekatze izaten jarraitzen ez duen parekatze hura da. Honako irudian parekatze maximal bana azaltzen da hiru grafotarako: Parekatze osoa grafoko ertz guztiak hartzen dituena da. Txandakazko ibilbidea parekatutako eta parekatu gabeko ertzak txandakatzen dituena da. Ibilbide gehitzailea parekatu gabeko ertz batean hasi eta bukatzen den txandakazko ibilbidea da. Elementu ezberdinak lotu edo parekatu behar direlarik, parekatzeen kopurua handiena izatea bilatzen denean erabiltzen dira parekatzearen alorreko kontzeptuak. Adibidez, langile ezberdinak lan ezberdinetara esleitu nahi ditugunean, burutu beharreko lan kopurua maximotu nahi denean erabil daiteke parekatzea. Esleipen bakoitzak kostu edo etekin ezberdinak dituenean, sortzen da. (eu)
- En matemática discreta y en particular en la teoría de grafos, un apareamiento o conjunto independiente de aristas, también llamado emparejamiento o matching (en inglés), en un grafo es un conjunto de aristas independientes, es decir, sin vértices en común. (es)
- In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. (en)
- En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. (fr)
- Nella disciplina matematica della teoria dei grafi, un accoppiamento o abbinamento (in inglese matching) o insieme degli spigoli indipendenti in un grafo è un insieme bipartito di spigoli senza vertici comuni. Può trattarsi anche di un intero grafo composto da spigoli senza vertici comuni. (it)
- 그래프 이론에서 부합(附合, 영어: matching 매칭[*])은 서로 만나지 않는 변들의 집합이다. (ko)
- グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。 極大マッチング、最大マッチングは必ず存在するが、完全マッチングは存在するとは限らない。（例: 奇数個頂点のグラフ） (ja)
- Als een niet-gerichte normale graaf is met knopenverzameling en zijdenverzameling , dan is de zijdenverzameling een koppeling (Engels: matching) als geen twee zijden van een gemeenschappelijke knoop hebben. Twee knopen die verbonden zijn door een zijde uit een koppeling zijn gekoppeld en elkaars partner. De andere knopen zijn vrij of ongebonden. (nl)
- Skojarzenie (ang. matching) – podzbiór krawędzi grafu (ozn. ) o tej własności, że każdy wierzchołek jest końcem co najwyżej jednej krawędzi z . Pary wierzchołków połączone bezpośrednio krawędzią należącą do są skojarzone przez Wierzchołki będące końcami krawędzi należących do są M-nasycone. Wierzchołki niebędące końcami krawędzi należących do są M-nienasycone. Skojarzenie maksymalne (ang. maximal matching) – takie skojarzenie w grafie że po dodaniu dowolnej krawędzi spośród krawędzi do tego skojarzenia, przestaje ono być skojarzeniem. Skojarzenie największe (ang. maximum matching) – takie skojarzenie w grafie że nie istnieje skojarzenie o większej liczbie krawędzi. Skojarzenie doskonałe (albo „pełne”, ang. perfect matching) – podzbiór krawędzi grafu o tej własności, że każdy wierzchołek jest M-nasycony. Aby w grafie istniało skojarzenie doskonałe, musi on mieć parzystą liczbę wierzchołków. Skojarzenie doskonałe jest zawsze skojarzeniem największym i maksymalnym. W grafie może być wiele skojarzeń doskonałych. Ścieżka przemienna (ang. alternating path) – ścieżka ułożona naprzemiennie z krawędzi grafu należących i nienależących do .
* Skojarzenie w grafie (czerwone krawędzie)
* Skojarzenie maksymalne (liczba krawędzi 3)
* Skojarzenie największe (liczba krawędzi 4)
* Skojarzenie doskonałe
* Inne skojarzenie doskonałe (pl)
- В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер. (ru)
- En matchning är inom matematik, specifikt grafteori, en mängd av bågar (kanter) i en graf sådan att inget par av bågar har någon gemensam nod. Motsvarande begrepp med noder istället för bågar kallas för oberoende mängd. (sv)
- Na teoria dos grafos um acoplamento, emparelhamento ou conjunto de arestas independentes em um grafo G é um conjunto de arestas sem vértices em comum. Em outras palavras, dado um grafo G, um acoplamento M (do inglês Matching) é subconjunto de arestas de G tal qual todo vértice em G é extremo de, no máximo, uma aresta em M. G pode ser ainda um grafo inteiro consistindo de arestas sem vértices comuns. (pt)
- 在图论中，一个图是一个匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边，而每一条边都将一对顶点相匹配。 (zh)
- Парування, або незалежний набір ребер, або паросполука графу — множина ребер без спільних вершин (несуміжних). (uk)
|
| rdfs:comment
|
- للمقارنة بين رسمين بيانيين، انظر مطابقة الرسوم البيانية. في الانضباط الرياضي لنظرية الرسم البياني، تكون الحافة المطابقة أو المستقلة المحددة في الرسم البياني عبارة عن مجموعة من الحواف بدون رؤوس شائعة. في بعض التطابقات، قد تكون جميع الرؤوس حادثة مع بعض حافة المطابقة، ولكن هذا ليس مطلوبًا ولا يمكن أن يحدث إلا إذا كان عدد الرؤوس حتى. يمكن العثور على العثور على مطابقة في ثنائي المسار كمشكلة تدفق الشبكة (ar)
- En la disciplina matemàtica de la teoria de grafs, un aparellament d'un graf és un conjunt d'arestes sense vèrtexs en comú. També pot ser un graf complet que consisteixi d'arestes sense vèrtexs comuns. L'aparellament bipartit és un cas especial d'un problema sobre una xarxa de flux. (ca)
- Párování grafu je v teorii grafů taková podmnožina hran grafu, že žádné dvě hrany z této množiny nemají společný vrchol. Idea je taková, že vrcholy grafů dáváme do párů. Pár může vzniknout jen tam, kde byla hrana. Přitom každý vrchol může být jen v jednom páru. Řadu praktických problémů lze převést na algoritmizované hledání jistého typu párování v grafu. (cs)
- En matemática discreta y en particular en la teoría de grafos, un apareamiento o conjunto independiente de aristas, también llamado emparejamiento o matching (en inglés), en un grafo es un conjunto de aristas independientes, es decir, sin vértices en común. (es)
- In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. (en)
- En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. (fr)
- Nella disciplina matematica della teoria dei grafi, un accoppiamento o abbinamento (in inglese matching) o insieme degli spigoli indipendenti in un grafo è un insieme bipartito di spigoli senza vertici comuni. Può trattarsi anche di un intero grafo composto da spigoli senza vertici comuni. (it)
- 그래프 이론에서 부합(附合, 영어: matching 매칭[*])은 서로 만나지 않는 변들의 집합이다. (ko)
- グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。 極大マッチング、最大マッチングは必ず存在するが、完全マッチングは存在するとは限らない。（例: 奇数個頂点のグラフ） (ja)
- Als een niet-gerichte normale graaf is met knopenverzameling en zijdenverzameling , dan is de zijdenverzameling een koppeling (Engels: matching) als geen twee zijden van een gemeenschappelijke knoop hebben. Twee knopen die verbonden zijn door een zijde uit een koppeling zijn gekoppeld en elkaars partner. De andere knopen zijn vrij of ongebonden. (nl)
- В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер. (ru)
- En matchning är inom matematik, specifikt grafteori, en mängd av bågar (kanter) i en graf sådan att inget par av bågar har någon gemensam nod. Motsvarande begrepp med noder istället för bågar kallas för oberoende mängd. (sv)
- Na teoria dos grafos um acoplamento, emparelhamento ou conjunto de arestas independentes em um grafo G é um conjunto de arestas sem vértices em comum. Em outras palavras, dado um grafo G, um acoplamento M (do inglês Matching) é subconjunto de arestas de G tal qual todo vértice em G é extremo de, no máximo, uma aresta em M. G pode ser ainda um grafo inteiro consistindo de arestas sem vértices comuns. (pt)
- 在图论中，一个图是一个匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边，而每一条边都将一对顶点相匹配。 (zh)
- Парування, або незалежний набір ребер, або паросполука графу — множина ребер без спільних вершин (несуміжних). (uk)
- Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird. Folgende Situation wird dabei betrachtet: Gegeben sei eine Menge von Dingen und zu diesen Dingen Informationen darüber, welche davon einander zugeordnet werden könnten. Ein Matching (in der Literatur manchmal auch Paarung) ist dann als eine solche Auswahl aus den möglichen Zuordnungen definiert, die kein Ding mehr als einmal zuordnet. Die am häufigsten gestellten Fragen in dieser Situation sind dann die folgenden: (de)
- Grafo bateko parekatzea erpin edo puntu komunik ez duten ertzen multzo bat da, elkarren ondokoak ez diren ertzen multzo bat alegia. Erpin bat parekatua dela esaten da parekatzearen ertz baten mutur batean badago. Bestela parekatu gabe dagoela esaten da. Parekatze maximoa ahalik eta ertz kopuru handiena biltzen duen parekatzea da. Grafo batean parekatze maximo bat baino gehiago izan daiteke. Honako irudian parekatze maximo bana azaltzen da hiru grafotarako: Parekatze osoa grafoko ertz guztiak hartzen dituena da. Txandakazko ibilbidea parekatutako eta parekatu gabeko ertzak txandakatzen dituena da. (eu)
- Skojarzenie (ang. matching) – podzbiór krawędzi grafu (ozn. ) o tej własności, że każdy wierzchołek jest końcem co najwyżej jednej krawędzi z . Pary wierzchołków połączone bezpośrednio krawędzią należącą do są skojarzone przez Wierzchołki będące końcami krawędzi należących do są M-nasycone. Wierzchołki niebędące końcami krawędzi należących do są M-nienasycone. Skojarzenie maksymalne (ang. maximal matching) – takie skojarzenie w grafie że po dodaniu dowolnej krawędzi spośród krawędzi do tego skojarzenia, przestaje ono być skojarzeniem.
* Skojarzenie w grafie (czerwone krawędzie)
*
*
*
* (pl)
|
