Cycle (théorie des graphes)

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Cycle.

Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle.

Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).

Le terme de cycle désigne parfois aussi le graphe cycle constitué d'un cycle élémentaire de longueur n.

Terminologie

Si la chaine est élémentaire, c'est-à-dire ne passe pas deux fois par un même sommet, alors on parle de cycle élémentaire. Un cycle élémentaire ne contient pas d'autre cycle. Dans un cycle élémentaire, chaque sommet a un degré égal à deux.

La longueur d'un cycle élémentaire est le nombre de ses arêtes (ou de ses sommets). Étant donné un graphe , la longueur minimale de ses cycles s'appelle la maille de , tandis que la longueur maximale de ses cycles s'appelle la circonférence de .

Si, dans un graphe, deux sommets d'un cycle sont reliés par une arête qui n'appartient pas au cycle, cette arête est appelée corde du cycle. Un cycle de G est induit dans lorsqu'il n'a pas de cordes. Un graphe est dit cordal ou triangulé si chacun de ses cycles de quatre sommets ou plus possède une corde.

Lorsque le cycle contient un nombre impair (réciproquement pair) d'arêtes on l'appelle un cycle impair (réciproquement cycle pair).

Dans les graphes pondérés, le poids d'un cycle est la somme des poids des arêtes qu'il contient. Si ce poids est négatif, on parle de cycle absorbant.

Présence de cycles

Théorème — Un graphe simple de degré minimal possède un cycle de longueur au moins égale à .

Démonstration

comporte au moins une chaine, puisque . Soit la plus longue de ces chaînes.

Considérons les voisins de . Ils font tous partie de cette chaine, car sinon on pourrait construire une chaine plus longue en concaténant un voisin n'appartenant pas à la chaine.

Soit le voisin dont l'indice est minimal (c.à.d. le plus éloigné de ). Le long de la chaine, est situé à au moins sommets de car le graphe est simple. Comme , le sommet est au moins à sommets de via cette chaine.

Le cycle est ainsi de longueur au moins égale à .

Un graphe non orienté sans cycles s'appelle une forêt. Le théorème précédent a pour conséquence qu'une forêt comporte forcément des sommets de degré zéro (isolés) ou de degré un (feuilles). Cette condition n'est pas suffisante, un graphe de degré minimal zéro ou un peut quand même comporter des cycles.

Problèmes liés

  • Le problème du cycle hamiltonien consiste à trouver un cycle élémentaire passant par tous les sommets.
  • Le problème du cycle eulérien consiste à trouver un cycle passant exactement une fois par chaque arête.
  • Le problème du postier chinois consiste à trouver un plus court cycle passant au moins une fois par chaque arête.

Voir aussi

Read other articles:

الجدول الزمني لحرب لبنان 2006 (يوليو)

  لمعانٍ أخرى، طالع الجدول الزمني لحرب لبنان 2006 (توضيح). هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أغسطس 2017) هذا هو الجدول الزمني لحرب لبنان 2006 خلال شهر يوليو. 12 يوليو المقالة الرئيسة: عملية الوعد الصادق حز�...

 

Swivel

Connection that allows an object to rotate horizontally or vertically For other uses, see Swivel (disambiguation). A swivel in a chain link Stainless steel anchor swivel A swivel in a link A swivel is a connection that allows the connected object, such as a gun, chair, swivel caster, or an anchor rode to rotate horizontally or vertically. Swivel designs A common design for a swivel is a cylindrical rod that can turn freely within a support structure. The rod is usually prevented from slipping...

 

Diatessaron

Ne doit pas être confondu avec la quarte parfaite en musique, appelée diatessaron par les pythagoriciens. Fragment du Diatessaron, parchemin de Doura-Europos n° 24 (IIIe siècle), Dura Parchment 24 (en). Uncial 0212 (dans la numérotation Gregory-Aland). Le Diatessaron, littéralement « à travers quatre », est une harmonie des Évangiles écrite en syriaque[1],[2] vers l'an 170 de notre ère [3] au IIe siècle. Il est aussi connu sous le nom Evangelion Damhalte ܐܶ...

Emu

Large flightless bird endemic to Australia For other uses, see Emu (disambiguation). EmuTemporal range: Middle Miocene – present PreꞒ Ꞓ O S D C P T J K Pg N Miocene–present[1] Conservation status Least Concern  (IUCN 3.1)[2] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Infraclass: Palaeognathae Order: Casuariiformes Family: Casuariidae Genus: Dromaius Species: D. novaehollandiae Binomial name Dromaius novaeholland...

 

VentureBeat

American technology news and analysis website based in San Francisco This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: VentureBeat – news · newspapers · books · scholar · JSTOR (November 2015) (Learn ho...

 

Oxford Centre for Hindu Studies

Academic institution at Oxford The Oxford Centre for Hindu StudiesEstablished1997; 27 years ago (1997)FocusThe study of Hindu culture, religion, languages, literature, philosophy, history, arts and society, in all periods and in all parts of the world.ChairThe Lord Navnit Dholakia OBE PC DLDirectorShaunaka Rishi DasKey peopleProf Gavin Flood, Dr Nicholas Sutton, Dr Jessica Frazier, Dr Rembert Lutjerharms, Dr Bjarne Wernicke-Olesen, Anuradha DooneySubsidiariesThe Bhumi Projec...

Hotel McAlpin

Residential building in Manhattan, New York Herald TowersThe hotel building as seen in 2011Former namesHotel McAlpinGeneral informationLocation1282-1300 BroadwayManhattan, New YorkCoordinates40°44′57″N 73°59′16″W / 40.74917°N 73.98778°W / 40.74917; -73.98778Construction started1911Completed1912Height308 feet (94 m)Technical detailsFloor count25Design and constructionArchitect(s)Frank Mills AndrewsReferences[1] Herald Towers, formerly the Hotel...

 

1750 au Canada

Éphémérides Fort Lawrence - Mount allison University Archieves, Robert Cunningham fonds, 1755.Chronologie du Canada 1747 1748 1749  1750  1751 1752 1753Décennies au Canada :1720 1730 1740  1750  1760 1770 1780 Chronologie dans le monde 1747 1748 1749  1750  1751 1752 1753Décennies :1720 1730 1740  1750  1760 1770 1780Siècles :XVIe XVIIe  XVIIIe  XIXe XXeMillénaires :-Ier Ier  IIe  IIIe Chronologies thémat...

 

Філософія

Частина серії проФілософіяLeft to right: Plato, Kant, Nietzsche, Buddha, Confucius, AverroesПлатонКантНіцшеБуддаКонфуційАверроес Філософи Епістемологи Естетики Етики Логіки Метафізики Соціально-політичні філософи Традиції Аналітична Арістотелівська Африканська Близькосхідна іранська Буддій�...

Black lounge suit

Men's semi-formal daytime attire This article is about a specific dress code. For black lounge suits in general, see lounge suit. U.K. Prime Minister Winston Churchill in 1943, giving his famous 'V' sign during World War II on Downing Street, London, wearing a black lounge suit with formal trousers, dotted bowtie, dark waistcoat, homburg hat, and a walking stick Part of a series onWestern dress codesand corresponding attires Formal (full dress)   White tie  Morning dress  Full ...

 

Mount Sneffels

Mountain in Colorado, United States For the town named after this mountain, see Sneffels, Colorado. Mount SneffelsView of Mount Sneffels from the northHighest pointElevation14,150 ft (4315.4 m)[1][2]NAVD88Prominence3050 ft (930 m)[3]Isolation15.71 mi (25.3 km)[3]ListingNorth America highest peaks 51stUS highest major peaks 37thColorado highest major peaks 18thColorado fourteeners 27thColorado county high points 16thCoordinates38°00′14″N 107°47′32�...

 

Kottankulangara Devi Temple

Hindu temple in Kerala, India Kottankulangara Devi TempleReligionAffiliationHinduismDistrictKollamDeityGoddess Durga Bhagavathy or Aadi ShakthiFestivalsChamayavilakkuLocationLocationChavaraStateKeralaCountry IndiaKottankulangara Devi Temple, Chavara, Kollam, KeralaGeographic coordinates8°58′46″N 76°32′06″E / 8.97958°N 76.53512°E / 8.97958; 76.53512 [1]SpecificationsTemple(s)OneElevation31.65 m (104 ft)Websitehttp://kottankulangaratemp...

Kyoto Animation

Kyoto Animation Co., Ltd.Nama asli株式会社京都アニメーションJenisKabushiki gaishaIndustriAnimasi JepangNovel ringanDidirikan1981; 43 tahun lalu (1981)KantorpusatUji, Prefektur Kyoto, Jepang[1]TokohkunciHideaki Hatta (Presiden)[2]Yoko Hatta (Wakil Presiden)[3]Karyawan130 (Oktober 2010)[4]AnakusahaAnimation Do (Osaka)[5]Situs webwww.kyotoanimation.co.jp Kyoto Animation Co., Ltd. (株式会社京都アニメーションcode: ja is depreca...

 

حرب ثورة 17 فبراير

ثورة 17 فبراير جزء من الربيع العربي   سيطر عليها المعارضون بحلول 1 آذار. (مرقطة: استعادها الموالون قبل التدخل الأمي في 19 آذار.)   مناطق متنازع عليها بين آذار وآب.   التقدم في الجبهة الغربية خلال آب.   سيطر عليها المعارضون بحلول 1 تشرين الأول..   آخر معاقل ...

 

1976 Pulitzer Prize

The following are the Pulitzer Prizes for 1976. Journalism awards Public Service: The Anchorage Daily News, for its disclosures of the impact and influence of the Teamsters Union on Alaska's economy and politics.[1] Local General or Spot News Reporting: Gene Miller of The Miami Herald, for his persistent and courageous reporting over eight and one-half years that led to the exoneration and release of two men who had twice been tried for murder and wrongfully convicted and sentenced to...

List of acts of the Parliament of the United Kingdom from 1803

Part of a series onBritish law Acts of Parliament of the United Kingdom Year      1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 ...

 

Клавдий

У этого термина существуют и другие значения, см. Клавдий (значения). Тиберий Клавдий Цезарь Август Германиклат. Tiberius Claudius Caesar Augustus Germanicus Римский император 24 января 41 — 13 октября 54 Предшественник Калигула Преемник Нерон Рождение 1 августа 10 до н. э.(-010-08-01)Лугдун Смерт�...

 

Inland Flyer

Inland Flyer backing away from a landing, circa 1904. History NameInland Flyer Owner; La Conner Trading & Trans. Co.; Puget Sound Nav. Co. RoutePuget Sound, Hood Canal Completed1898 IdentificationUS registry #100660[1] FateDismantled, machinery reused, hull converted to fish barge 1916 General characteristics Typeinland steamboat Tonnage151 gross; 103 regist.[1] Length105.5 ft (32.16 m)[1] Beam32.1 ft (9.78 m)[1] Depth4.8 ft (1.46&...

Stasiun Sakaimachi

Stasiun Sakaimachi境町駅Pintu keluar Stasiun Sakaimachi pada September 2021Lokasi432 Sakaidodo, Isesaki-shi, Gunma-ken 370-0117JepangKoordinat36°16′37″N 139°15′23″E / 36.2770°N 139.2563°E / 36.2770; 139.2563Operator Tōbu RailwayJalur Jalur Tōbu IsesakiLetak106.3 km dari AsakusaJumlah peron2 peron sampingInformasi lainKode stasiunTI-22Situs webSitus web resmiSejarahDibuka27 Maret 1910PenumpangFY20191569 per hari Lokasi pada petaStasiun SakaimachiLokasi...

 

Claudia Kolb

American swimmer (born 1949) Claudia KolbKolb in 1970Personal informationFull nameClaudia Anne KolbNational teamUnited StatesBorn (1949-12-19) December 19, 1949 (age 74)Hayward, CaliforniaHeight5 ft 7 in (1.70 m)Weight134 lb (61 kg)SportSportSwimmingStrokesBreaststroke, individual medleyClubSanta Clara Swim ClubCoachGeorge Haines Medal record Women's swimming Representing the United States Olympic Games 1968 Mexico City 200 m medley 1968 Mexico City 400...