Grafo ciclo

Grafo ciclo $C_{n}$
ciclo C₆
Vértices	n
Aristas	n
Cintura	n
Automorfismos	2n (D_n)
Número cromático	2 si n es par 3 si n es impar
Índice cromático	2 si n es par 3 si n es impar
Propiedades	2-conexo por vértices 2-conexo por aristas 2-regular Euleriano Hamiltoniano orientable
[editar datos en Wikidata]

En teoría de grafos, un grafo ciclo o simplemente ciclo es un grafo que consiste en un camino simple cerrado, es decir, en el que no se repite ningún vértice, salvo el primero con el último. Un grafo ciclo de n vértices se denota $C_{n}$ . El número de vértices en un grafo ciclo es igual al número de aristas. En su versión más común, como grafo no dirigido, cada vértice tiene grado 2, por lo que es un grafo 2-regular; en su versión dirigida, en cambio, se trata de un grafo 1-regular.

Definición formal

Si $G(V,E)\,$ es un grafo ciclo $C_{n}$ , el grafo tiene $n$ vértices $V=\{v_{1},v_{2},\ldots ,v_{n}\}$ y $n$ aristas formadas de la siguiente manera:

E=\{\{v_{i},v_{i+1}\}|i=1,...,n-1\}\cup \{v_{n},v_{1}\}

Propiedades

Un grafo ciclo es:

2-conexo

En efecto, si tomamos 2 vértices cualquiera, siempre hay 2 caminos disjuntos (sin vértices comunes a excepción de los vértices extremos) que los conectan. Luego, por el Teorema de Whitney (1932), los ciclos tienen índice de conexión: $\kappa \,(C_{n})=2$ .

Los ciclos son también 2-conexo por aristas, en efecto, dado 2 vértices cualquiera, siempre hay 2 caminos distintos (sin aristas comunes entre ambos) que los conectan. Luego, por el Teorema de Menger (1927), los ciclos tienen índice de arista conexión: $\kappa _{a}\,(C_{n})=2$ .

Los ciclos al tener el índice de arista conexión igual a 2 carecen de aristas puentes.

2-regular

Es claro que los ciclos son 2-regulares, ya que dado un ciclo de n vértices, todos sus grados son iguales a dos: $\delta (v_{i})=2\,$ con i=1,...,n

Euleriano

En efecto, los ciclos al ser conexos y 2-regulares satisfacen el Teorema de Euler(1736)-Hierholzer(1873). Luego, los ciclos contienen un Circuito euleriano.

Hamiltoniano

Es fácil ver que también contienen un ciclo hamiltoniano.

Coloración

$\chi (C_{n})={\begin{cases}2,&{\mbox{si }}n{\mbox{ es par}}\\3,&{\mbox{si }}n{\mbox{ es impar}}\end{cases}}$

Coloración por aristas

$\chi '(C_{n})={\begin{cases}2,&{\mbox{si }}n{\mbox{ es par}}\\3,&{\mbox{si }}n{\mbox{ es impar}}\end{cases}}$

Grafo ciclo dirigido

Un grafo ciclo dirigido es una versión dirigida de un grafo ciclo, con todas las aristas orientadas hacia una misma dirección.

En un grafo ciclo dirigido, el grado de salida del vértice es 1 y el de entrada también es 1.

$\delta _{s}(x)=\delta _{e}(x)=1\,$

Si las aristas del grafo no están orientadas en una misma dirección, entonces se habla de «semiciclo» en lugar de «ciclo».^[1]

Grafos ciclo signados

El signo de un grafo ciclo signado o con signos es igual al producto de los signos de las aristas incluidas en el grafo, calculado de acuerdo a una conjunción lógica:^[1]

(+)(+) = +
(+)(–) = –
(–)(+) = –
(–)(–) = +

Por lo tanto, un grafo ciclo con un número par de aristas negativas tendrá un signo positivo, y un grafo ciclo con un número impar de aristas negativas, tendrá un signo negativo. Note que todo lo anterior se mantiene para un grafo semiciclo dirigido.^[1]

Véase también

Referencias

↑ ^a ^b ^c Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.

Bibliografía

Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.

Enlaces externos

Weisstein, Eric W. «Cycle Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. . (MathWorld discusses both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams in the same article.)
Luca Trevisan, Characters and Expansion.

Datos: Q622506
Multimedia: Cycle graphs / Q622506

Read other articles:

دورة فرنسا المفتوحة 1986

دورة فرنسا المفتوحة 1986 رقم الفعالية 85 البلد فرنسا التاريخ 1986 الرياضة كرة المضرب الفعاليات دورة فرنسا المفتوحة 1986 - فردي السيدات، ودورة فرنسا المفتوحة 1986 - فردي الرجال، ودورة فرنسا المفتوحة 1986 - زوجي السيدات، ودورة فرنسا المفتوحة 1986 – زوجي رجال ...

Marcelo (football, 1987)

Pour les articles homonymes, voir Marcelo et Guedes. Marcelo Marcelo avec le PSV Eindhoven en 2011. Situation actuelle Équipe Western Sydney Wanderers Numéro 6 Biographie Nom Marcelo Antônio Guedes Filho Nationalité Brésilienne Naissance 20 mai 1987 (36 ans) São Vicente (Brésil) Taille 1,91 m (6′ 3″) Période pro. 2007- Poste Défenseur central Pied fort ambidextre Parcours junior Années Club 2004-2007 Santos FC 0 0 Parcours senior1 AnnéesClub 0M.0(B.) 2007-2008 S...

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

Распространение немецкого языка в мире

Немецкий язык является одним из наиболее часто используемых языков в мире, занимая среди всех языков десятое место по популярности[1]. Также он является одним из наиболее распространённых языков: на немецком говорит более 100 млн человек во всём мире[2]. При этом ну�...

Сибирский горный козёл

Сибирский горный козёл Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:СинапсидыКла�...

Ain El Delb

Village in South Governorate, LebanonAin El Delb عين الدلبVillageAin El DelbLocation in LebanonCoordinates: 33°32′28″N 35°23′18″E / 33.541104°N 35.388272°E / 33.541104; 35.388272Country LebanonGovernorateSouth GovernorateDistrictSidon DistrictTime zoneUTC+2 (EET) • Summer (DST)UTC+3 (EEST) Ain El Delb (عين الدلب) is a small village in the Sidon District of the South Governorate in Lebanon. History In 1875 Victor Guérin foun...

إحصائيات تصادم السيارات

الوفيات الناجمة عن حوادث المرور على الطرق لكل 100000 السكان في عام 2012.[1] لا توجد بيانات أقل من 5 5-10 10-15 15-20 20-25 25-30 30-35 35-40 أكثر من 40 الوفيات الناجمة عن حوادث الطرق لكل مليار مركبة في عام 2004 لايوجد ...

فلوريان ماير (حكم كرة قدم)

لمعانٍ أخرى، طالع فلوريان ماير (توضيح). فلوريان ماير معلومات شخصية الميلاد 21 نوفمبر 1968 (العمر 55 سنة)براونشفايغ الجنسية ألمانيا تعديل مصدري - تعديل فلوريان ماير (بالألمانية: Florian Meyer)‏ (مواليد 21 نوفمبر 1968 في براونشفايغ) حكم كرة قدم ألماني .[1][2][3] بدأ مس...

البطولة الوطنية التونسية 1992–93

البطولة الوطنية التونسية 1992–93 تفاصيل الموسم 1992–93 النسخة 38 البلد تونس المنظم الجامعة التونسية لكرة القدم البطل الترجي الرياضي التونسي (11) مباريات ملعوبة 182 عدد المشاركين 14 أهداف مسجلة 408 معدل الأهداف 2.24 الهداف عبد القادر بلحسن كنيت ماليتولي (18)[1] 1991–92 1993�...

10 Things We Should Do Before We Break Up

Artikel ini membutuhkan ringkasan cerita. Buat ringkasan cerita untuk membantu pembaca memahami artikel dengan lebih baik. (May 2022) 10 Things We Should Do Before We Break UpPosterSutradaraGalt NiederhofferDitulis olehGalt NiederhofferPemeranChristina RicciHamish LinklaterTanggal rilis 21 Februari 2020 (2020-02-21) Durasi74 menitNegaraAmerika SerikatBahasaInggris 10 Things We Should Do Before We Break Up adalah film romansa Amerika Serikat tahun 2020 yang ditulis dan disutradarai oleh G...

2018–19 FA Trophy

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: 2018–19 FA Trophy – news · newspapers · books · scholar · JSTOR (September 2020) Football tournament season 2018–19 FA TrophyFootball Association TrophyTournament detailsCountryEnglandGuernseyWalesDefending championsBrackley TownFinal positionsCha...

Langues franciques

Pour les articles homonymes, voir Francique. Langues germaniques occidentales de 580, des parlers vieux franciques en vert, le deux plus au nord-ouest en bleu sont les autres dialectes vieux franciques Les langues et dialectes franciques sont un groupe linguistique au sein des langues germaniques occidentales. Le groupe francique rassemble des langues et dialectes appartenant à la fois au bas francique, au moyen allemand et à l'allemand supérieur, c'est donc un regroupement polyphylétiqu...

Barranquilla

Capital district of Atlántico Department in Colombia District and city in Caribbean, ColombiaBarranquillaDistrict and cityFrom the top: Bolivar walk, Panoramic, Aduana building, Cathedral, Caribbean Cultural Park, Republican mansion. FlagSealNickname(s): La Puerta de Oro de Colombia(Spanish for 'Colombia's Golden Gate')Motto(s): Ven vive Barranquilla(Ven vive Barranquilla)Atlántico DepartmentBarranquillaShow map of ColombiaBarranquillaShow map of South AmericaCoordinates: ...

Coat of arms of the Polish–Lithuanian Commonwealth

Polish–Lithuanian coat of arms Coat of arms of the Polish-Lithuanian CommonwealthArmigerKing of Poland/Grand Duke of LithuaniaAdoptedFollowing 1386[Note 1][citation needed]ShieldQuarterly 1st and 4th Gules, an eagle argent, crowned or; 2nd and 3rd, Gules, Pogonia.[1][2][3][4] The coat of arms of the Polish–Lithuanian Commonwealth was the symbol of the Polish–Lithuanian Commonwealth, representing the union of the Crown of the Polish Kingdom...

Inondations de juillet 2021 en Europe

Inondations et crues de juillet 2021 en EuropeFauquemont, Pays-Bas, le 15 juillet 2021.LocalisationPays Allemagne Autriche Belgique Croatie France Italie Luxembourg Pays-Bas Roumanie Royaume-Uni Suisse TurquieRégions affectées EuropeCaractéristiquesType Crues et inondationsCumul des précipitations 182 mm à Cologne 207 mm à ReifferscheidHauteur de crue maximale Meuse : 6,70 mDébit maximal 4 000 m3/sDate de formation 14 et 15 juillet 2021ConséquencesNombre ...

Sukhumi

Aqãa/Sukhumicittà(AB) Аҟәа(KA) სოხუმი Aqãa/Sukhumi – Veduta LocalizzazioneStato Georgia (de iure) Abcasia (de facto) Regione Repubblica Autonoma Abcasa MunicipalitàSukhumi TerritorioCoordinate43°00′N 41°01′E43°00′N, 41°01′E (Aqãa/Sukhumi) Altitudine20 m s.l.m. Superficie27 km² Abitanti39 100 (2010) Densità1 448,15 ab./km² Altre informazioniLingueAbcaso (ufficiale), russo e georgiano Cod. postale384900 e 6600 Fuso or...

Solar wind

Stream of charged particles from the Sun For other uses, see Solar wind (disambiguation). Ulysses's observations of solar wind speed as a function of helio latitude during solar minimum. Slow wind (≈400 km/s) is confined to the equatorial regions, while fast wind (≈750 km/s) is seen over the poles.[1] Red/blue colors show outward/inward polarities of the heliospheric magnetic field. An illustration of the structure of the Sun GranulesSunspotPhotosphereChromosphereConvect...

كوفينغتون (تكساس)

لمعانٍ أخرى، طالع كوفينغتون (توضيح). كوفينغتون الإحداثيات 32°10′37″N 97°15′26″W / 32.1769°N 97.2572°W / 32.1769; -97.2572 [1] تقسيم إداري البلد الولايات المتحدة[2] التقسيم الأعلى مقاطعة هيل خصائص جغرافية المساحة 2.14431 كيلومتر مربع (1 أبريل 2010) ارت...

Fungsi eksponensial

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Fungsi eksponensial – berita · surat kabar · buku · cendekiawan · JSTORBagian dari serial artikel mengenaie Artikel mengenai e 2.718 281 828 459 045 235 360 287 … {\displaystyle 2.718\,281\,828\,4...

Leang Leangnge 1

Leang Leangnge 1Gua Leangnge 1LokasiKabupaten Pangkajene dan Kepulauan, Sulawesi Selatan, IndonesiaGeologikarst / batu kapur / batu gamping tipe Formasi TonasaSitus Leang Leangnge 1Nama sebagaimana tercantum dalamSistem Registrasi Nasional Cagar Budaya Cagar budaya IndonesiaPeringkatKabupaten/KotaKategoriSitusLokasikeberadaanKabupaten Pangkajene dan Kepulauan, Sulawesi Selatan, IndonesiaPemilik IndonesiaPengelolaKolaboratif antara Balai TN Babul, Pemerintah Kabupaten Pangkajene dan Kepul...