| dbo:abstract
|
- En teoria de grafs, el lema de l'encaixada de mans afirma que cada graf no dirigit té un nombre parell de vèrtexs de grau senar (el grau d'un vèrtex és el nombre d'arestes que el toquen). El nom prové d'una versió més col·loquial del lema: si algunes de les persones d'un encontre s'encaixen la mà, un nombre parell de persones l'haurà encaixat amb un nombre senar d'altres. El lema de l'encaixada de mans és una conseqüència de la fórmula de la suma de graus, per un graf amb un conjunt de vèrtexs V i un conjunt d'arestes E. Ambdós resultats els demostrà Leonhard Euler en el cèlebre problema dels set ponts de Königsberg, que inicià l'estudi de la teoria de grafs. Els vèrtexs de grau senar d'un graf sovint s'anomenen nodes senars o vèrtexs senars; amb aquesta terminologia, el lema de l'encaixada de mans es pot formular com que cada graf té un nombre parell de vèrtexs senars. (ca)
- In der Graphentheorie besagt das Handschlaglemma, dass in jedem endlichen einfachen Graphen die Summe der Grade aller Knoten genau doppelt so groß ist wie die Anzahl seiner Kanten. Formal heißt das: Ist ein Graph und bezeichnet den Grad des Knotens (bei gerichteten Graphen werden sowohl die Ein- als auch die Ausgangs-Grade gezählt), so gilt Daraus folgt sofort, dass jeder Graph eine gerade Anzahl von Knoten ungeraden Grades hat. Bei regulären Graphen vereinfacht sich die Formel. Für einen -regulären Graphen gilt Das Handschlaglemma wurde im Rahmen des Königsberger Brückenproblems 1736 von Leonhard Euler bewiesen. Der Name des Handschlaglemmas kommt von dem Beispiel, dass die Anzahl der Personen auf einer Party, die einer ungeraden Zahl von Gästen die Hand geben, gerade ist. (de)
- In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. In more colloquial terms, in a party of people some of whom shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees (the numbers of times each vertex is touched) equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory. Beyond the Bridges of Königsberg and their generalization to Euler tours, other applications include proving that for certain combinatorial structures, the number of structures is always even, and assisting with the proofs of Sperner's lemma and the mountain climbing problem. The complexity class PPA encapsulates the difficulty of finding a second odd vertex, given one such vertex in a large implicitly-defined graph. (en)
- En théorie des graphes, une branche des mathématiques, le lemme des poignées de main est la déclaration selon laquelle chaque graphe non orienté fini a un nombre pair de sommets de degré impair. Plus trivialement, dans une réunion de plusieurs personnes dont certaines se serrent la main, un nombre pair de personnes devra serrer un nombre impair de fois la main d'autres personnes. (fr)
- Nella teoria dei grafi il lemma di handshaking è l'affermazione che ogni grafo non orientato finito ha un numero pari di vertici con grado dispari (il numero di archi che toccano il vertice). In termini più colloquiali, in un gruppo di persone alcune delle quali si stringono la mano, un numero pari di persone deve aver stretto la mano di un numero dispari di altre persone. I vertici di grado dispari in un grafo sono talvolta chiamati nodi dispari o vertici dispari; in questa terminologia, il lemma di handshaking può essere riformulato come l'affermazione che ogni grafo ha un numero pari di nodi dispari. Il lemma di handshaking è una conseguenza della formula della somma dei gradi (a volte chiamato a sua volta lemma di handshaking), per un grafo con insieme di vertici V e archi E. Entrambi i risultati furono provati da Leonhard Euler (1736) nel suo famoso articolo sui sette ponti di Königsberg che iniziò lo studio della teoria dei grafi. Altre applicazioni includono la dimostrazione che per alcune strutture combinatorie, il numero di strutture è sempre pari, e l'assistenza con le prove del lemma di Sperner e del problema del "mountain climbing" (in italiano "alpinismo"). La classe di complessità PPA incapsula la difficoltà di trovare un secondo vertice dispari, dato uno di questi vertici in un grande grafo definito implicitamente. (it)
- Dany jest graf prosty o wierzchołkach i krawędziach. Na mocy lematu o uściskach dłoni spełniona jest następująca własność: Powyższą własność nietrudno jest zrozumieć intuicyjnie: każda krawędź łączy dwa wierzchołki, a zatem dodając do siebie stopnie sąsiadujących wierzchołków (czyli liczby krawędzi wychodzących z nich), liczymy każdą z krawędzi dwukrotnie, co potwierdza prawdziwość powyższej własności. Wynika z tego również fakt, że w dowolnym grafie liczba wierzchołków o nieparzystych stopniach jest parzysta. Jako pierwszy zauważył tę własność Leonhard Euler w 1736 roku. (pl)
- Na teoria do grafos, um ramo da matemática, o lema do aperto de mão é a afirmação que todo grafo não-direcionado finito tem um número par de vértices de grau ímpar (o número de arestas ligadas ao vértice). Em termos coloquiais, num grupo de pessoas das quais algumas apertam mãos, um número par de pessoas deve ter apertado um número ímpar de mãos de outras pessoas. O lema do aperto de mãos é uma consequência da fórmula da soma dos graus (também chamado às vezes de lema do aperto de mão), para um grafo com conjunto de vértices V e conjunto de arestas E. Ambos os resultados foram provados por Leonhard Euler (1736) no seu artigo famoso sobre o problema das Sete pontes de Königsberg que iniciou o estudo da teoria dos grafos. Os vértices de grau ímpar em um grafo são às vezes chamados de nós ímpares ou vértices ímpares; nessa terminologia, o lema do aperto de mão pode ser reescrito como a afirmação que todo grafo possui um número par de nós ímpares. (pt)
- У теорії графів, галузі математики, Лема про рукостискання є твердженням, що у кожного кінцевого неорієнтованого графу є парне число вершин із непарним степенем (число граней, що інцидентні вершині). Якщо простіше, у групі людей, які обмінюються рукостисканнями, є парне число людей, які напевно потиснули непарну кількість рук інших людей. Лема про рукостискання — наслідок формули суми степенів (яку також іноді називають лемою про рукостискання). Для графа з множиною вершин V і множиною ребер Е. Обидва результати довів Леонард Ейлер (1736) у своїй відомій роботі про Сім мостів Кеніґсберґа, з якої починається теорія графів. Вершини непарного степеня в графі іноді називають непарними вузлами або непарними вершинами. У цій термінології лему про рукостискання можна переформулювати як твердження, що кожен граф має парне число непарних вузлів. (uk)
- Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других людей, чётно. Лемма является следствием формулы суммы степеней, также иногда называемой леммой о рукопожатиях: для графа с множеством вершин и множеством рёбер . Оба результата доказаны Эйлером в докладе о семи мостах Кёнигсберга (1736), положившем начало исследованиям в области теории графов. Вершины нечётных степеней графа иногда называются нечётными вершинами или нечётными узлами; используя эту терминологию, можно перефразировать лемму таким образом: каждый граф имеет чётное число нечётных вершин. Формула суммы степеней подразумевает, что -регулярный граф с числом вершин имеет рёбер; в частности, если нечётно, число рёбер должно делиться на . Лемма неприменима к бесконечным графам, даже если они имеют конечное число нечётных вершин. Например, бесконечный путь с одной концевой вершиной имеет единственную нечётную вершину (то есть, нечётное количество). Лемма использована в одном из доказательств леммы Шпернера, а также «». (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 29033 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
| |
| dbp:caption
|
- 6 (xsd:integer)
- , its number of edges. (en)
- The rhombic dodecahedron is biregular with six vertices of degree four and eight vertices of degree three; (en)
- Schematic view of Königsberg's seven bridges (en)
- The Clebsch graph, regular of degree five, has an even number of vertices and a number of edges that is a multiple of five. (en)
- Graph with vertices for each land mass and an edge for each bridge (en)
|
| dbp:first
| |
| dbp:image
|
- 7 (xsd:integer)
- Clebsch Lombardi.svg (en)
- Königsberg graph.svg (en)
- Rhombicdodecahedron.jpg (en)
|
| dbp:last
| |
| dbp:totalWidth
|
- 400 (xsd:integer)
- 500 (xsd:integer)
|
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie des graphes, une branche des mathématiques, le lemme des poignées de main est la déclaration selon laquelle chaque graphe non orienté fini a un nombre pair de sommets de degré impair. Plus trivialement, dans une réunion de plusieurs personnes dont certaines se serrent la main, un nombre pair de personnes devra serrer un nombre impair de fois la main d'autres personnes. (fr)
- Dany jest graf prosty o wierzchołkach i krawędziach. Na mocy lematu o uściskach dłoni spełniona jest następująca własność: Powyższą własność nietrudno jest zrozumieć intuicyjnie: każda krawędź łączy dwa wierzchołki, a zatem dodając do siebie stopnie sąsiadujących wierzchołków (czyli liczby krawędzi wychodzących z nich), liczymy każdą z krawędzi dwukrotnie, co potwierdza prawdziwość powyższej własności. Wynika z tego również fakt, że w dowolnym grafie liczba wierzchołków o nieparzystych stopniach jest parzysta. Jako pierwszy zauważył tę własność Leonhard Euler w 1736 roku. (pl)
- En teoria de grafs, el lema de l'encaixada de mans afirma que cada graf no dirigit té un nombre parell de vèrtexs de grau senar (el grau d'un vèrtex és el nombre d'arestes que el toquen). El nom prové d'una versió més col·loquial del lema: si algunes de les persones d'un encontre s'encaixen la mà, un nombre parell de persones l'haurà encaixat amb un nombre senar d'altres. El lema de l'encaixada de mans és una conseqüència de la fórmula de la suma de graus, (ca)
- In der Graphentheorie besagt das Handschlaglemma, dass in jedem endlichen einfachen Graphen die Summe der Grade aller Knoten genau doppelt so groß ist wie die Anzahl seiner Kanten. Formal heißt das: Ist ein Graph und bezeichnet den Grad des Knotens (bei gerichteten Graphen werden sowohl die Ein- als auch die Ausgangs-Grade gezählt), so gilt Daraus folgt sofort, dass jeder Graph eine gerade Anzahl von Knoten ungeraden Grades hat. Bei regulären Graphen vereinfacht sich die Formel. Für einen -regulären Graphen gilt (de)
- In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. In more colloquial terms, in a party of people some of whom shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees (the numbers of times each vertex is touched) equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory. (en)
- Nella teoria dei grafi il lemma di handshaking è l'affermazione che ogni grafo non orientato finito ha un numero pari di vertici con grado dispari (il numero di archi che toccano il vertice). In termini più colloquiali, in un gruppo di persone alcune delle quali si stringono la mano, un numero pari di persone deve aver stretto la mano di un numero dispari di altre persone. I vertici di grado dispari in un grafo sono talvolta chiamati nodi dispari o vertici dispari; in questa terminologia, il lemma di handshaking può essere riformulato come l'affermazione che ogni grafo ha un numero pari di nodi dispari. (it)
- Na teoria do grafos, um ramo da matemática, o lema do aperto de mão é a afirmação que todo grafo não-direcionado finito tem um número par de vértices de grau ímpar (o número de arestas ligadas ao vértice). Em termos coloquiais, num grupo de pessoas das quais algumas apertam mãos, um número par de pessoas deve ter apertado um número ímpar de mãos de outras pessoas. O lema do aperto de mãos é uma consequência da fórmula da soma dos graus (também chamado às vezes de lema do aperto de mão), (pt)
- Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других людей, чётно. Лемма является следствием формулы суммы степеней, также иногда называемой леммой о рукопожатиях: для графа с множеством вершин и множеством рёбер . Оба результата доказаны Эйлером в докладе о семи мостах Кёнигсберга (1736), положившем начало исследованиям в области теории графов. (ru)
- У теорії графів, галузі математики, Лема про рукостискання є твердженням, що у кожного кінцевого неорієнтованого графу є парне число вершин із непарним степенем (число граней, що інцидентні вершині). Якщо простіше, у групі людей, які обмінюються рукостисканнями, є парне число людей, які напевно потиснули непарну кількість рук інших людей. Лема про рукостискання — наслідок формули суми степенів (яку також іноді називають лемою про рукостискання). (uk)
|
| rdfs:label
|
- Lema de l'encaixada de mans (ca)
- Handschlaglemma (de)
- Handshake (matematica) (it)
- Handshaking lemma (en)
- Lemme des poignées de main (fr)
- Lemat o uściskach dłoni (pl)
- Лемма о рукопожатиях (ru)
- Lema do aperto de mão (pt)
- Лема про рукостискання (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
