Handshaking lemma (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/6n-graf.svg?width=300 |
| dbo:wikiPageID | 9607933 (xsd:integer) |
| dbo:wikiPageLength | 29033 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097816533 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Root-finding_algorithms dbr:End_(graph_theory) dbr:Multigraph dbr:Nash_equilibrium dbr:Euler_path dbr:Euler_tour dbr:Algorithmic_game_theory dbr:Path_graph dbr:Regular_graph dbr:Rhombic_dodecahedron dbr:Cubic_graph dbr:Undirected_graph dbr:Degree_(graph_theory) dbr:Double_counting_(proof_technique) dbr:Incidence_matrix dbr:Connectivity_(graph_theory) dbr:Mathematical_induction dbr:Glossary_of_graph_theory dbr:Multiset dbr:Leonhard_Euler dbr:Clebsch_graph dbr:Complete_(complexity) dbr:Complexity_class dbr:Component_(graph_theory) dbr:Computational_complexity_theory dbr:PPA_(complexity) dbr:Parity_(mathematics) dbr:Path_(graph_theory) dbr:Piecewise_linear_function dbr:Tibor_Gallai dbr:Travelling_salesman_problem dbr:Edge_(graph_theory) dbr:Fixed-point_theorem dbr:Cardinality dbr:Cedric_Smith_(statistician) dbr:Directed_graph dbr:Fair_division dbr:Family_of_sets dbr:Graph_theory dbr:Reconstruction_conjecture dbr:Hexagon dbr:Kaliningrad dbr:Bipartite_graph dbr:Biregular_graph dbc:Lemmas_in_graph_theory dbr:Symmetric_relation dbr:Hex_(board_game) dbr:Hobby–Rice_theorem dbr:Sperner's_lemma dbr:Michael_Krivelevich dbr:Christofides_algorithm dbr:Proof_by_cases dbr:Unit_interval dbr:Loop_(graph_theory) dbr:Unit_square dbr:Vertex_(graph_theory) dbr:Seven_Bridges_of_Königsberg dbr:Parallelogram dbr:Mountain_climbing_problem dbr:Unordered_pair dbr:PPAD_(complexity) dbr:Hamiltonian_cycle dbr:Implicitly-defined_graph dbr:File:6n-graf.svg dbr:File:Infinite_graph_one_direction.svg dbr:File:Mountain_climbing_problem.gif dbr:File:Sperner2d.svg |
| dbp:authorlink | Leonhard Euler (en) |
| 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 | Leonhard (en) |
| dbp:image | 7 (xsd:integer) Clebsch Lombardi.svg (en) Königsberg graph.svg (en) Rhombicdodecahedron.jpg (en) |
| dbp:last | Euler (en) |
| dbp:totalWidth | 400 (xsd:integer) 500 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Good_article dbt:Harvtxt dbt:Main dbt:Multiple_image dbt:R dbt:Reflist dbt:Short_description dbt:Harvs |
| dbp:year | 1736 (xsd:integer) |
| dct:subject | dbc:Lemmas_in_graph_theory |
| rdf:type | yago:WikicatLemmas yago:WikicatMathematicalTheorems yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Lemma106751833 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| 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 | freebase:Handshaking lemma yago-res:Handshaking lemma wikidata:Handshaking lemma dbpedia-ca:Handshaking lemma dbpedia-de:Handshaking lemma dbpedia-fa:Handshaking lemma dbpedia-fr:Handshaking lemma dbpedia-he:Handshaking lemma dbpedia-hu:Handshaking lemma http://hy.dbpedia.org/resource/Ձեռքսեղմումների_լեմմա dbpedia-it:Handshaking lemma dbpedia-pl:Handshaking lemma dbpedia-pt:Handshaking lemma dbpedia-ru:Handshaking lemma http://ta.dbpedia.org/resource/கைகொடுத்தல்_தேற்றம் dbpedia-th:Handshaking lemma dbpedia-uk:Handshaking lemma https://global.dbpedia.org/id/55jcc |
| prov:wasDerivedFrom | wikipedia-en:Handshaking_lemma?oldid=1097816533&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Sperner2d.svg wiki-commons:Special:FilePath/6n-graf.svg wiki-commons:Special:FilePath/Rhombicdodecahedron.jpg wiki-commons:Special:FilePath/7_bridges.svg wiki-commons:Special:FilePath/Königsberg_graph.svg wiki-commons:Special:FilePath/Infinite_graph_one_direction.svg wiki-commons:Special:FilePath/Mountain_climbing_problem.gif wiki-commons:Special:FilePath/Clebsch_Lombardi.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Handshaking_lemma |
| is dbo:wikiPageRedirects of | dbr:Odd_node dbr:Odd_vertex dbr:Handshake_lemma dbr:Handshaking_Lemma dbr:Handshaking_theorem dbr:Degree_sum_formula |
| is dbo:wikiPageWikiLink of | dbr:Petersen's_theorem dbr:Regular_graph dbr:Cubic_graph dbr:Degree_(graph_theory) dbr:Double_counting_(proof_technique) dbr:Glossary_of_graph_theory dbr:Erdős–Gallai_theorem dbr:Line_graph dbr:Logic_of_graphs dbr:Chinese_postman_problem dbr:Snark_(graph_theory) dbr:Deltahedron dbr:Hamiltonian_path_problem dbr:PPA_(complexity) dbr:TFNP dbr:Dual_graph dbr:Edge_coloring dbr:Eulerian_path dbr:Pancake_graph dbr:Parity_of_zero dbr:Handshake_(disambiguation) dbr:Hypohamiltonian_graph dbr:Thrackle dbr:Sperner's_lemma dbr:Implicit_graph dbr:Ramsey's_theorem dbr:Christofides_algorithm dbr:Mountain_climbing_problem dbr:Odd_node dbr:Odd_vertex dbr:Handshake_lemma dbr:Handshaking_Lemma dbr:Handshaking_theorem dbr:Degree_sum_formula |
| is foaf:primaryTopic of | wikipedia-en:Handshaking_lemma |
