Kínaipostás-probléma

A kínaipostás-probléma, más néven útbejárási probléma a gráfelmélet egyik kérdése: legkevesebb hány élismétléssel lehet bejárni egy gráfot úgy, hogy minden élen áthaladjunk legalább egyszer?[1]

A problémát Kuan Mej-ku (管梅谷)(wd) vetette fel egy 1962-ben megjelent cikkében, amely a postások útvonalának optimizálásáról szólt. Ennek alapján az Amerikai Egyesült Államok Szabványügyi Hivatalánál dolgozó Alan J. Goldman javasolta a kínaipostás-probléma elnevezést.[2]

Ha létezik a gráfban Euler-kör, akkor az egyben egy optimális kínaipostás-útvonal. A postás tényleges útvonalán a többször bejárt éleket megfelelő multiplicitású többszörös éleknek tekintve olyan gráfot kapunk, aminek van Euler-köre. Semelyik élen nem érdemes kettőnél többször átmenni. A feladat azzal ekvivalens, hogy minimum hány él megduplázásával tehető olyanná a gráf, hogy legyen benne Euler-kör, azaz hogy minden csúcs fokszáma páros legyen. (Az összefüggőséget eleve feltételezzük.) Erre van jól működő algoritmus.[3][4]

Jegyzetek

  1. ↑ Chinese Postman Problem. mathworld.wolfram.com (Hozzáférés: 2020. január 16.)
  2. ↑ Chinese postman problem. xlinux.nist.gov (Hozzáférés: 2020. január 16.)
  3. ↑ Útbejárási probléma. www.tankonyvtar.hu (Hozzáférés: 2020. január 16.)
  4. ↑ Kínai postás probléma. www.math.u-szeged.hu (Hozzáférés: 2020. január 16.)

Kapcsolódó szócikkek

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!

Read other articles:

Juna Cinta Juni

Juna Cinta JuniGenre Drama Roman Komedi PembuatMD EntertainmentDitulis olehSabrina FirdausSkenarioSabrina FirdausSutradaraDinesh Sambi BoengPemeran Randy Pangalila Amanda Ajun Perwira Estelle Linden Adam Jordan Nafa Urbach Dicky Wahyudi Ria Irawan Virnie Ismail Roy Sungkono Adly Fairuz Penggubah lagu temaIndra OktianaLagu pembukaKamulah Orangnya — Indra OktinaLagu penutupKamulah Orangnya — Indra OktinaNegara asalIndonesiaBahasa asliBahasa IndonesiaJmlh. musim1Jmlh. episode29 (daftar epis...

 

Мечеть-собор Кордови

Мечеть-собор Кордови Дата створення / заснування 786 Країна  Іспанія[1][2][…] Адміністративна одиниця Кордова[1][2][…] Дієцезія Кордовська діоцезія Присвячено Небовзяття Діви Марії Каталожний код MV-01[4] Архітектор Ернан Руїз Id[5], Хуан де Очоаd[...

 

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

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

Stenocorus

Stenocorus Stenocorus meridianus Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Kelas: Insecta Ordo: Coleoptera Famili: Cerambycidae Subfamili: Lepturinae Tribus: Rhagiini Genus: Stenocorus Stenocorus adalah genus kumbang tanduk panjang yang berasal dari famili Cerambycidae. Genus ini juga merupakan bagian dari ordo Coleoptera, kelas Insecta, filum Arthropoda, dan kingdom Animalia. Larva kumbang dalam genus ini biasanya mengebor ke dalam kayu dan dapat menyebabkan kerusakan pada bat...

 

Elegance

Conceptual beauty that shows unusual effectiveness and simplicity Elegant redirects here. For the American novelist, see Robert Elegant. For other uses, see Elegance (disambiguation). Elegance of the Epoque by Frédéric Soulacroix An example of beauty in method—a simple and elegant proof of the Pythagorean theorem. Elegance is beauty that shows unusual effectiveness and simplicity. Elegance is frequently used as a standard of tastefulness, particularly in visual design, decorative arts, li...

 

Retro style

Historically derivative styles Retro redirects here. For other uses, see Retro (disambiguation). Retro clothing style, new Mini with old styling, retro transport (replica penny farthing bicycles) Retro style is imitative or consciously derivative of lifestyles, trends, or art forms from history, including in music, modes, fashions, or attitudes. In popular culture, the nostalgia cycle is typically for the two decades that begin 20–30 years ago.[1] Definition The term retro has been ...

Vessillo Bartoli

Vessillo Bartoli Nazionalità  Italia Calcio Ruolo Allenatore (ex centrocampista) Termine carriera 1941 – giocatore1967 – allenatore CarrieraSquadre di club1 1931-1932 Vado? (?)1932-1935 Savona? (?)1935-1936 Savona? (?)1937-1938 Vado? (?)1938-1939 Imperia? (?)Carriera da allenatore 1950-1953 Sp. Luqueño1954 Paraguay1957-1958 Vado1961-1962 Cerro Porteño1965 Universidad Católica1967 El Nacional 1 I due numeri indicano le presenze e ...

 

Богота

У этого термина существуют и другие значения, см. Богота (значения). ГородБоготаисп. Bogotá Флаг Герб[d] 4°35′56″ с. ш. 74°04′51″ з. д.HGЯO Страна  Колумбия Регион Столичный округ Мэр Карлос Фернандо Галан[en] История и география Основан 6 августа 1538 Прежние названи�...

 

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国 フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期） フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

迪奥斯达多·马卡帕加尔

迪奥斯达多·马卡帕加尔Diosdado Pangan Macapagal第9任菲律賓總統任期1961年12月30日—1965年12月30日前任卡洛斯·P·加西亚继任费迪南德·马科斯第6任菲律賓副總統任期1957年12月30日—1961年12月30日前任卡洛斯·P·加西亚继任伊曼纽尔·佩莱斯 个人资料出生(1910-09-28)1910年9月28日 美屬菲律賓馬尼拉逝世1997年4月21日(1997歲—04—21)（86歲） 菲律賓馬卡迪墓地 菲律賓馬卡迪達義市英...

 

中華民國國軍中的中共間諜列表

 本表是動態列表，或許永遠不會完結。歡迎您參考可靠來源來查漏補缺。 潛伏於中華民國國軍中的中共間諜列表收錄根據公開資料來源，曾潛伏於中華民國國軍、被中國共產黨聲稱或承認，或者遭中華民國政府調查審判，為中華人民共和國和中國人民解放軍進行間諜行為的人物。以下列表以現今可查知時間為準，正確的間諜活動或洩漏機密時間可能早於或晚於以下所歸�...

 

Sacredness

Dedicated or set apart for the service or worship of a deity For other uses, see Sacred (disambiguation). Sanctity redirects here. For other uses, see Sanctity (disambiguation). Sacred describes something that is dedicated or set apart for the service or worship of a deity;[1] is considered worthy of spiritual respect or devotion; or inspires awe or reverence among believers. The property is often ascribed to objects (a sacred artifact that is venerated and blessed), or places (sacred...

European Foundation for the Improvement of Living and Working Conditions

European Foundation for the Improvement of Living and Working ConditionsAgency overviewFormedMay 1975 (1975-05)JurisdictionEuropean UnionHeadquartersWyattville Rd, Loughlinstown, Dublin, Ireland D18 KP65Agency executivesIvailo Kalfin, DirectorJan Kouwenberg, Chairperson of the Management BoardKey documentRegulation (EU) 2019/127Websiteeurofound.europa.eu The European Foundation for the Improvement of Living and Working Conditions (Eurofound) is an agency of the European Union which...

 

Paul Samuelson

American economist (1915–2009) Paul SamuelsonSamuelson in 2009BornPaul Anthony Samuelson(1915-05-15)May 15, 1915Gary, Indiana, U.S.DiedDecember 13, 2009(2009-12-13) (aged 94)Belmont, Massachusetts, U.S.EducationUniversity of Chicago (BA)Harvard University (MA, PhD)Spouses Marion Crawford ​ ​(m. 1938; died 1978)​[4] Risha Clay ​(m. 1981)​[5] Academic careerInstitutionMassachusetts Institute of T...

 

Circumcision

Removal of the human foreskin Not to be confused with female circumcision. For the paintings, see The Circumcision. CircumcisionCircumcision surgery with hemostats and scissorsICD-10-PCSZ41.2ICD-9-CMV50.2MeSHD002944OPS-301 code5–640.2MedlinePlus002998eMedicine1015820[edit on Wikidata] Circumcision is a procedure that removes the foreskin from the human penis. In the most common form of the operation, the foreskin is extended with forceps, then a circumcision device may be placed, a...

アヤックス・アムステルダム

アヤックス・アムステルダム 原語表記 Amsterdamsche Football Club Ajax愛称 de Godenzonen（神々の子）[1][2]de Joden（ユダヤ人）I Lancieri（槍騎兵）Lucky Ajaxクラブカラー     赤    白創設年 1900年所属リーグ エールディヴィジ所属ディビジョン 1部（2023-24）昨季リーグ順位 3位（2022-23）ホームタウン アムステルダムホームスタジアム ヨハン・クライフ�...

 

Maad Ibrahim

Questa voce sull'argomento calciatori iracheni è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Maad IbrahimNazionalità Iraq Calcio RuoloDifensore CarrieraSquadre di club1 ????Al Rasheed? (?) Nazionale ???? Iraq1+ (?) 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campionato.Il simbolo → indica un trasferimento in prestito.   Modifica dati su Wikidata · ...

 

Mauriceville railway station

Defunct railway station in New Zealand MauricevilleNew Zealand Government Railways (NZGR)regional railMauriceville railway station name board. December 2008.General informationLocationOpaki Kaiparoro Road, Mauriceville, New ZealandCoordinates40°46′45.08″S 175°42′0.42″E / 40.7791889°S 175.7001167°E / -40.7791889; 175.7001167Elevation220 metres (720 ft)Owned byRailways DepartmentLine(s)Wairarapa LineDistance110.56 kilometres (68.70 mi) from Wellingt...

Lafayette (Louisiane)

Pour les articles homonymes, voir Lafayette. Cet article est une ébauche concernant une localité de la Louisiane. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. LafayetteGéographiePays  États-UnisÉtat LouisianeParoisse Paroisse de Lafayette (chef-lieu)Chef-lieu AcadianeSuperficie 127,83 km2 (2010)Surface en eau 0,25 %Altitude 11 mGéographie Géographie de Lafayette (en)Coordonnées 30° ...

 

I Still Can't Get Over Loving You

1983 single by Ray Parker Jr.I Still Can't Get Over Loving YouSingle by Ray Parker Jr.from the album Woman Out of Control B-sideShe Still Feels the NeedReleasedOctober 1983Genre Pop rock synth-pop[1] Length4:09LabelArista - Arista 9116Songwriter(s)Ray Parker Jr.Producer(s)Ollie E. Brown and Ray Parker Jr.Ray Parker Jr. singles chronology The People Next Door (1983) I Still Can't Get Over Loving You (1983) Woman Out of Control (1984) I Still Can't Get Over Loving You is a 1983 song wri...