{"id":256,"date":"2021-12-28T21:27:12","date_gmt":"2021-12-28T21:27:12","guid":{"rendered":"http:\/\/blog.espol.edu.ec\/adguale\/?p=256"},"modified":"2021-12-29T08:06:58","modified_gmt":"2021-12-29T08:06:58","slug":"el-teorema-de-redei","status":"publish","type":"post","link":"https:\/\/blog.espol.edu.ec\/adguale\/2021\/12\/28\/el-teorema-de-redei\/","title":{"rendered":"El teorema de R\u00e9dei"},"content":{"rendered":"<p>Un grafo completo es un grafo simple en el todo v\u00e9rtice est\u00e1 conectado a todos los v\u00e9rtices restantes. Si a este grafo completo le damos direcci\u00f3n a sus enlaces obtendremos un grafo dirigido, al cual le llamaremos <em>torneo<\/em>.<\/p>\n<p>Una trayectoria hamiltoniana es una trayectoria que pasa por todos los v\u00e9rtices del grafo. En 1934 R\u00e9dei prob\u00f3 un teorema b\u00e1sico sobre torneos y lo hizo usando un argumento de inducci\u00f3n.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Teorema<\/strong>. (Teorema de R\u00e9dei) Todo torneo tiene una trayectoria Hamiltoniana dirigida.<\/p>\n<p><em>Demostraci\u00f3n.<\/em><\/p>\n<p>Usaremos inducci\u00f3n sobre el n\u00famero de v\u00e9rtices.<\/p>\n<p>Caso base: <span class=\"wp-katex-eq\" data-display=\"false\">n=1<\/span> .\u00a0El torneo trivial (sobre un v\u00e9rtice) tiene una trayectoria Hamiltoniana dirigida.<\/p>\n<p>&nbsp;<\/p>\n<p>Paso inductivo. Supongamos ahora que <span class=\"wp-katex-eq\" data-display=\"false\">n\\geq 2 <\/span> y que todo torneo sobre <span class=\"wp-katex-eq\" data-display=\"false\">n-1<\/span> v\u00e9rtices tiene una trayectoria Hamiltoniana dirigida. Sea\u00a0 <span class=\"wp-katex-eq\" data-display=\"false\">T<\/span> un torneo sobre <span class=\"wp-katex-eq\" data-display=\"false\">n <\/span> v\u00e9rtices y sea <span class=\"wp-katex-eq\" data-display=\"false\"> v\\in V(T)<\/span>. El digrafo <span class=\"wp-katex-eq\" data-display=\"false\">T'=T-v<\/span> es un torneo sobre <span class=\"wp-katex-eq\" data-display=\"false\"> n-1 <\/span> v\u00e9rtices y por hip\u00f3tesis de inducci\u00f3n tiene una trayectoria Hamiltoniana dirigida <span class=\"wp-katex-eq\" data-display=\"false\">P'=v_1v_2..v_{n-1}<\/span>.<\/p>\n<p>&nbsp;<\/p>\n<p>Caso 1: <span class=\"wp-katex-eq\" data-display=\"false\"> (v, v_1) <\/span> es un arco. En este caso la trayectoria Hamiltoniana buscada es <span class=\"wp-katex-eq\" data-display=\"false\"> T=v\\cup T'<\/span><\/p>\n<p>Caso 2: <span class=\"wp-katex-eq\" data-display=\"false\"> (v_{n-1}, v) <\/span> es un arco. En este caso la trayectoria Hamiltoniana buscada es <span class=\"wp-katex-eq\" data-display=\"false\"> T= T'\\cup v <\/span><\/p>\n<p>Caso 3: <span class=\"wp-katex-eq\" data-display=\"false\"> (v_1, v) y (v, v_{n-1}) <\/span> son arcos. En este caso existe un <span class=\"wp-katex-eq\" data-display=\"false\">v_j <\/span> tal que\u00a0 <span class=\"wp-katex-eq\" data-display=\"false\"> (v_j, v)<\/span> y <span class=\"wp-katex-eq\" data-display=\"false\">(v, v_{j+1})<\/span> son arcos. En tal caso la trayectoria <span class=\"wp-katex-eq\" data-display=\"false\">T<\/span> buscada ser\u00eda <span class=\"wp-katex-eq\" data-display=\"false\"> T=v_1 v_2.. v_j v v_{j+1}..v_{n-1}<\/span>.<\/p>\n<p>De lo que se concluye la prueba.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un grafo completo es un grafo simple en el todo v\u00e9rtice est\u00e1 conectado a todos los v\u00e9rtices restantes. Si a este grafo completo le damos direcci\u00f3n a sus enlaces obtendremos un grafo dirigido, al cual le llamaremos torneo. Una trayectoria hamiltoniana es una trayectoria que pasa por todos los v\u00e9rtices del grafo. En 1934 R\u00e9dei &hellip; <a href=\"https:\/\/blog.espol.edu.ec\/adguale\/2021\/12\/28\/el-teorema-de-redei\/\" class=\"more-link\">Sigue leyendo <span class=\"screen-reader-text\">El teorema de R\u00e9dei<\/span><\/a><\/p>\n","protected":false},"author":5810,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1419472],"tags":[],"class_list":["post-256","post","type-post","status-publish","format-standard","hentry","category-teoria-de-grafos"],"_links":{"self":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/256","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/users\/5810"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/comments?post=256"}],"version-history":[{"count":13,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/256\/revisions"}],"predecessor-version":[{"id":266,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/256\/revisions\/266"}],"wp:attachment":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/media?parent=256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/categories?post=256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/tags?post=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}