קוד פרופר

עץ ממוספר המתאים לקוד פרופר 4445

בתורת הגרפים, קוד פרווּפֵר (Prüfer Sequence) הוא התאמה בין קבוצת העצים הממוספרים בעלי n צמתים לבין אוסף הווקטורים באורך n-2 המורכבים ממספרים טבעיים בין 1 לבין n, באופן שמהווה מעין קידוד של המידע שדרוש כדי ליצור את הגרף. את הקידוד יצר המתמטיקאי הגרמני היינץ פרווּפֵר (1896-1934) ב-1918, וסיפק בכך את ההוכחה הקונסטרוקטיבית הראשונה למשפט של קיילי (1889) שלפיו מספר העצים הפורשים של הגרף השלם הוא .

קוד פרופר הוא פונקציה חד-חד-ערכית ועל מאפשר לזהות בעיות ספירה של עצים ממוספרים כבעיות הנוגעות לתכונות של סדרות של מספרים ובכך מאפשר ייבוא של שיטות קומבינטוריות בסיסיות לפתרון בעיות מורכבות בתורת הגרפים.

תהליך הקידוד - מעבר מגרף לקוד

תהליך קידוד גרף בעל 6 צמתים לקוד פרופר
באדום - עלה בעל הערך הנמוך ביותר
בכתום - הצומת אליו העלה בעל הערך הנמוך מחובר. אותו נדרש להציב בקוד.
איקס - עלים שכבר נותחו בשלב הקודם ולכן לא נדרש לקחת אותם בחשבון

בהינתן עץ כלשהו וצומת כלשהו בתוכו נסמן ב- את העץ המתקבל על ידי הסרת הצומת v וכל הצלעות המחוברות אליו. סימון זה יאפשר להגדיר רקורסיבית את פעולת הקוד.

בכל שלב:

  1. נבחר את העלה (צומת בעץ המחובר לצומת אחד בלבד, כלומר צומת בעל דרגה 1) שמספרו הוא מינימלי.
  2. נרשום, במקום הבא בוקטור הקוד, את מספרו של הצומת היחיד שמחובר אליו.
  3. נמחק את העלה מהעץ

לאחר המחיקה נוצר עץ חדש עם מספר צמתים קטן באחד מהעץ המקורי, עליו נפעיל שוב את התהליך. התהליך יסתיים כאשר יישארו שני עלים המחוברים אחד לשני. היות שאורך הקוד שווה למספר צמתים שהוסרו - אורך הקוד הוא בעל n-2 איברים.

תהליך החילוץ - מעבר מקוד לגרף

מעבר מקוד פרופר "1344" לגרף עץ תואם

נציג פונקציה הופכית לקוד פרופר, כלומר, מעבר מוקטור באורך n-2 המכיל מספרים טבעיים מ-1 עד n לעץ תואם. נדרש להיעזר ברשימה של כל המספרים הטבעיים בין 1 ל-n ובוקטור הקוד. השלבים בתהליך:

  1. נחפש את המספר המינימלי ברשימה שאינו מופיע בוקטור הקוד, ונציב אותו כצומת בגרף.
  2. ניקח את הערך הראשון בוקטור ונציב כצומת בגרף
  3. נמתח קשת בין הצמתים שנוצרו בשני השלבים הקודמים
  4. נמחק את המספרים מהווקטור ומהרשימה

נחזור על השלבים שוב ושוב, לאחר n-2 שלבים יישארו ברשימה שני מספרים והווקטור יהיה ריק. נחבר את שני הצמתים האלו בקשת.

קישורים חיצוניים

ויקישיתוף מדיה וקבצים בנושא קוד פרופר בוויקישיתוף

Read other articles:

Bandar Udara Hiroshima広島空港Hiroshima Kūkō広島空港Hiroshima KūkōIATA: HIJICAO: RJOAInformasiJenisPublicPengelolaPemerintah Prefekturan HiroshimaLokasiMihara, Hiroshima, JapanKetinggian dpl mdplSitus webhij.airport.jpPetaRJOATitik lokasi di petaLandasan pacu Arah Panjang Permukaan m kaki 10/28 3.000 9.843 Aspal/beton Bandar Udara Hiroshima (広島空港code: ja is deprecated , Hiroshima Kūkō) (IATA: HIJ, ICAO: RJOA) merupakan nama bandara yang terletak di Hiroshi...

 

 

Wenche MyhreGitte, Wencke, Siw 2005 à FrancfortBiographieNaissance 15 février 1947 (77 ans)OsloNom de naissance Wenche Synnøve MyhrePseudonyme Wencke MyhreNationalité norvégienneActivités Actrice, artiste d'enregistrement, chanteuse, personne du monde du divertissementPériode d'activité depuis 1954Père Kjell Myhre (d)Fratrie Reidar Myhre (d)Conjoints Torben Friis Møller (d) (de 1969 à 1979)Michael Pfleghar (de 1981 à 1990)Arthur Buchardt (en) (de 1995 à 1999)Enfant Michael P...

 

 

Main article: 2024 United States presidential election 2024 United States presidential election in Wyoming ← 2020 November 5, 2024 2028 →   Nominee Donald Trump(presumptive) Joe Biden(presumptive) Party Republican Democratic Home state Florida Delaware Running mate TBA Kamala Harris(presumptive) Incumbent President Joe Biden Democratic Elections in Wyoming Federal government Presidential elections 1892 1896 1900 1904 1908 1912 1916 1920 1924 1928 1932 193...

Bolu province Bolu iliProvince of TurkeyLocation of Bolu Province in TurkeyCountryTurkeyRegionBlack SeaLuas • Total7.410 km2 (2,860 sq mi)Populasi (2010-12-31)[1] • Total271.208 • Kepadatan37/km2 (95/sq mi)Kode area telepon0374Pelat kendaraan14Situs webbolu.gov.tr Bolu (Turki: Bolu ili) adalah sebuah provinsi Turki. Galeri Mist early in the morning A scene from Yedigöller Bolu town Referensi ^ Turkish Statistical Instit...

 

 

Sporting event delegationTogo at the2008 Summer OlympicsIOC codeTOGNOCComité National Olympique Togolaisin BeijingCompetitors4 in 4 sportsFlag bearer Benjamin BoukpetiMedalsRanked 80th Gold 0 Silver 0 Bronze 1 Total 1 Summer Olympics appearances (overview)19721976–198019841988199219962000200420082012201620202024 Togo competed in the 2008 Summer Olympics held in Beijing, China from August 8 to August 24, 2008. At the men's slalom K-1 event, Benjamin Boukpeti won a bronze medal in canoe...

 

 

Pour les articles homonymes, voir d'Ornano. Rudolf-August d'OrnanoFonctionsConseiller général de l'Yonne1861-1865Député de l'Yonne4 septembre 1853 - 14 octobre 1865Préfet de l'Yonne1851-1853ChambellanNapoléon IIIBiographieNaissance 9 juin 1816 ou 9 juin 1817LiègeDécès 14 octobre 1865Paris ou château de la Branchoire (d)Sépulture Cimetière du Père-LachaiseNationalité françaiseFormation École spéciale militaire de Saint-CyrActivités Homme politique, haut fonctionnaireFamille ...

Lazarus menerima tepuk tangan berdiri dari Russell Simmons Tepuk tangan berdiri adalah sebuah bentuk tepuk tangan dimana para anggota penonton yang duduk kemudian berdiri sesambil tepuk tangan usai menonton penampilan luar biasa. Pemakaian kata tersebut dalam bahasa Inggris telah ada sejak setidaknya tahun 1831.[1] Wikimedia Commons memiliki media mengenai Standing ovation. Referensi ^ ovation. Dictionary.com. Online Etymology Dictionary. Douglas Harper, Historian. Accessed April 17, ...

 

 

У этого термина существуют и другие значения, см. Церера (значения). Церера Статуя Цереры Мифология древнеримская мифология Сфера влияния сельское хозяйство, зерно, фертильность и материнство[d] Латинское написание Ceres Пол женский Отец Сатурн Мать Опа Дети Л...

 

 

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Hungarian Working People's Party – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message) Political party in Hungary Hungarian Working People's Party Magyar Dolgozók PártjaFirst leaderMátyás RákosiLast l...

Este artículo o sección tiene referencias, pero necesita más para complementar su verificabilidad. Busca fuentes: «Vicente Sánchez» – noticias · libros · académico · imágenesEste aviso fue puesto el 26 de junio de 2022. Vicente Sánchez Datos personalesNombre completo Vicente Martín Sánchez BragundeApodo(s) Carucha, Tamborilero y La PesadillaNacimiento Montevideo, Uruguay7 de diciembre de 1979 (44 años)Nacionalidad(es) uruguayaAltura 1,70 m (5′ ...

 

 

1997 live album by Emerson, Lake & PalmerLive at the Isle of Wight Festival 1970Live album by Emerson, Lake & PalmerReleased1997RecordedIsle of Wight Festival29 August 1970GenreProgressive rockLength68:01LabelManticore RecordsSanctuary RecordsProducerEmerson, Lake & PalmerEmerson, Lake & Palmer chronology Live in Poland(1997) Live at the Isle of Wight Festival 1970(1997) Then & Now(1998) Professional ratingsReview scoresSourceRatingAllMusic[1]Classic Rock&...

 

 

Greek scholar (17th century) Ioannis Kottounios (Ioannes Cottunius)Born1577 (1577)Veroia, Ottoman EmpireDied1658 (aged 80–81)Padua, Republic of VeniceAlma materCollegio Pontifico GrecoUniversity of PaduaEraRenaissanceRegionWestern philosophyInstitutionsCollegio Pontifico GrecoUniversity of PaduaUniversity of BolognaMain interestsMedicine, Greek literature, theology and philosophy Ioannis Kottounios (Greek: Ἰωάννης Κωττούνιος, Latin: Joannes Cottunius de ...

Railway station in Namerikawa, Toyama Prefecture, Japan Higashi-Namerikawa Station東滑川駅Higashi-Namerikawa Station in August 2008General informationLocation1512 Nakamura, Namerkawa-shi, Toyama-ken 936-0002JapanCoordinates36°47′16″N 137°22′40″E / 36.7878°N 137.3779°E / 36.7878; 137.3779Operated by Ainokaze Toyama RailwayLine(s)■ Ainokaze Toyama Railway LineDistance62.1 km from KurikaraPlatforms2 side platformsTracks2Other informationStatusUnattendedW...

 

 

تعداد الولايات المتحدة 1960 المعلومات البلد الولايات المتحدة  التاريخ 1 أبريل 1960  تعداد الولايات المتحدة 1950  تعداد الولايات المتحدة 1970  تعديل مصدري - تعديل   تعداد الولايات المتحدة 1960 كان التعداد الثامن عشر للسكان يجرى في الولايات المتحدة.[1][2][3] تم إ�...

 

 

Mexican filmmaker and author (born 1964) Not to be confused with Guillermo de Torre. In this Spanish name, the first or paternal surname is del Toro and the second or maternal family name is Gómez. Guillermo del ToroDel Toro in 2023BornGuillermo del Toro Gómez[1] (1964-10-09) 9 October 1964 (age 59)Guadalajara, Jalisco, MexicoAlma materUniversity of GuadalajaraOccupationsFilm directorfilm producerscreenwriterauthorYears active1985–presentWorksFilmographySpou...

Town in Louisiana, United StatesMadisonville, LouisianaTownTown of MadisonvilleMadisonville Town HallLocation of Madisonville in St. Tammany Parish, Louisiana.MadisonvilleLocation in LouisianaShow map of LouisianaMadisonvilleLocation in the United StatesShow map of the United StatesCoordinates: 30°24′26″N 90°09′42″W / 30.40722°N 90.16167°W / 30.40722; -90.16167CountryUnited StatesStateLouisianaParishSt. TammanyFounded1800Named forJames MadisonGovernment...

 

 

هواوي بي 20معلومات عامةالنوع هاتف ذكي الصانع هواوي المطور هواوي عائلة المنتج سلسلة هواوي بي موقع الويب consumer.huawei.com… أهم التواريختاريخ الإصدار 27 مارس 2018 الخصائصنظام التشغيل إي إم يو آي البطارية مدخرة أيونات الليثيوم القياساتالأبعاد 149٫1 () × 70٫8 () × 7٫65 () مم الوزن 165 غرام الإصد�...

 

 

Pour les articles homonymes, voir Brda. Cet article est une ébauche concernant une localité monténégrine. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Brda (sr) Брда Héraldique Administration Pays Monténégro Municipalité Budva Indicatif téléphonique international +(382) Indicatif téléphonique local 033 Immatriculation BD Démographie Population de l'agglomération 0 hab. (2003) Géographi...

Palacio Real de Madrid Bien de interés culturalPatrimonio histórico de España Vista aérea del Palacio RealLocalizaciónPaís EspañaComunidad Comunidad de MadridLocalidad MadridDirección Calle Bailén, s/n. 28013Datos generalesCategoría MonumentoCódigo RI-51-0001061Declaración 4 de junio de 1931Construcción 1735 - 1764Estilo Barroco clasicistaMapa de localización Palacio Real de Madrid Ubicación en Madrid [editar datos en Wikidata] Mapa del entorno. Al oeste los jardines ...

 

 

For the linguistic term, see Inalienable possession. Part of a series onEconomic, applied, and development anthropology Basic concepts Commodification Barter Debt Finance Embeddedness Reciprocity Redistribution Value Wealth Gift economy Limited good Inalienable possessions Singularization (commodity pathway) Spheres of exchange Social capital Cultural capital Provisioning systems Hunting-gathering Pastoralism Nomadic pastoralism Shifting cultivation Moral economy Peasant economics Case studie...