גרף רגולרי

בתורת הגרפים, גרף רגולרי (באנגלית: Regular graph) הוא גרף שבו דרגת כל הקודקודים שווה, כלומר מספר הקשתות היוצאות מכל קודקוד קבוע. גרף מכוון רגולרי מקיים תנאים חזקים יותר ובו דרגת הכניסה ודרגת היציאה של כל הקודקודים שוות.^[1] כלומר $d^{+}(i)=d^{-}(i)=k$ לכל קודקוד $i$ .

גרף רגולרי שבו דרגת כל הקודקודים היא $k$ נקרא גרף $k$ -רגולרי או גרף רגולרי מדרגה $k$ .

לדוגמה, $K_{n}$ (גרף שלם בעל $n$ קודקודים) הוא גרף $(n-1)$ -רגולרי.

אם $k$ אי-זוגי, נובע מלמת לחיצות הידיים שבגרף $k$ -רגולרי יהיו מספר זוגי של קודקודים.

הייחודיות של הגרפים הרגולריים טמונה בעובדה שסדרת הדרגות שלהם קבועה.

תכונות אלגבריות

נסמן ב- $A$ את מטריצת הסמיכויות של הגרף $G$ . $G$ הוא גרף $k$ -רגולרי אם ורק אם ${\textbf {j}}=(1,\dots ,1)$ הוא וקטור עצמי של $A$ ששייך לערך העצמי $k$ .^[2]

יהיו $\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$ הערכים העצמיים של $A$ , $G$ גרף $k$ -רגולרי אם ורק אם מתקיים $k=\lambda _{0}$ ו- $\sum _{i=0}^{n-1}\lambda _{i}^{2}=n\lambda _{0}$ (כאשר $n$ הוא מספר הצמתים ב- $G$ ).^[2]

גרף רגולרי הוא קשיר אם ורק אם לערך העצמי $k=\lambda _{0}$ יש ריבוי אלגברי 1.^[3] הטענה ניתנת להכללה: מספר הרכיבים הקשירים של הגרף שווה לריבוי האלגברי של הערך העצמי $k=\lambda _{0}$ .^[2]

גרף רגולרי-חזק

גרף רגולרי-חזק הוא גרף רגולרי שבו לכל זוג של קודקודים שכנים (כלומר, יש בין הקודקודים קשת) יש $\lambda$ שכנים משותפים, ולכל זוג קודקודים לא שכנים יש $\mu$ שכנים משותפים.

גרף רגולרי-חזק לעיתים מסומן ב- $srg(v,k,\lambda ,\mu )$ ( $v$ מסמן את מספר הקודקודים בגרף, $k$ מסמן את הדרגה המשותפת לכל הקודקודים).

לדוגמה, גרף פטרסן (אנ') הוא גרף רגולרי-חזק שבו $10$ קודקודים, דרגת כל הצמתים היא $3$ , לכל זוג של קודקודים שכנים אין אף שכן משותף ולכל זוג קודקודים לא שכנים יש שכן משותף בודד. כלומר, ניתן לסמן אותו כך: $srg(10,3,0,1)$ .

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

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

גרף רגולרי, באתר MathWorld (באנגלית)
גרף רגולרי-חזק, באתר MathWorld (באנגלית)

הערות שוליים

^ Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. pp. 29. ISBN 978-981-02-1859-1.
^ ¹ ² ³ Stanic, Zoran, 2, Regular Graphs : A Spectral Approach, Berlin/Boston, GERMANY, 2017, עמ' 15-16, ISBN 978-3-11-035128-6
^ צד אחד של ההוכחה נובע ממשפט פרון-פרובניוס.

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

Read other articles:

Budai

Budai (Hanzi: 布袋; Pinyin: Bùdài), atau Hotei dalam bahasa Jepang,[1] Bố Đại dalam bahasa Vietnam, adalah dewa dalam mitologi Cina. Sering kali diasosiasikan dengan Buddha Maitreya atau Buddha Tertawa yang menggambarkan kebahagiaan. Banyak orang Barat yang bingung dengan perbedaan antara Buddha Gautama dan Maitreya. Penggambaran Budai secara tradisi digambarkan sebagai seorang biksu gendut dan memakai atau menggenggam tasbih. Dia membawa barang-barangnya dalam sebuah...

List of dams and reservoirs in New Jersey

Following is a list of dams and reservoirs in New Jersey. All major dams are linked below. The National Inventory of Dams defines any major dam as being 50 feet (15 m) tall with a storage capacity of at least 5,000 acre-feet (6,200,000 m3), or of any height with a storage capacity of 25,000 acre-feet (31,000,000 m3).[1] Dams and reservoirs in New Jersey Lake Carnegie, Princeton University Merrill Creek Reservoir This list is incomplete. You can help Wikipedia by expand...

Nanyue

Nanyue南越国204 SM–111 SMWilayah terluas Nanyue (ungu)Ibu kotaPanyuBahasa yang umum digunakanBahasa Tionghoa LamaBahasa Yue kunoPemerintahanMonarkiKaisar atau Raja • 204–137 SM Zhao Tuo• 137–122 SM Zhao Mo• 122–113 SM Zhao Yingqi• 113–112 SM Zhao Xing• 112–111 SM Zhao Jiande Perdana Menteri • ? –111 SM Lü Jia Sejarah • Perang Pasifikasi Dinasti Qin 218 SM• Pendirian 204 SM• Upeti Pertama untuk...

Chavo Guerrero Jr.

American professional wrestler Chavo Guerrero redirects here. For his father, see Chavo Guerrero Sr. Chavo Guerrero Jr.Guerrero in 2016Birth nameSalvador Guerrero IVBorn (1970-10-20) October 20, 1970 (age 53)[1]El Paso, Texas, U.S.[2][3]Spouse(s) Shari Guerrero (m. 1998)Children2FamilyGuerreroProfessional wrestling careerRing name(s)Chavo Guerrero Jr.[2][3]Chavo Guerrero[4]Kerwin White[5]Lieutenant Loc...

Linda Wagenmakers

Linda WagenmakersLinda Wagenmakers, 2021Lahir30 November 1975 (umur 48)Arnhem, BelandaPekerjaanPenyanyi, pengisi suara Linda Wagenmakers, 2009 Linda Wagenmakers (lahir 30 November 1975) adalah seorang penyanyi dan pengisi suara asal Belanda. Dia memulai karirnya pada usia 21 sebagai Kim dalam musikal Miss Saigon versi belanda.[1][2] Referensi ^ Linda Wagenmakers | Eurovision Song Contest 2012 in Baku. EuroVisionary. 2000-05-13. Diarsipkan dari versi asli tanggal Mar...

Stan Laurel

Pour les articles homonymes, voir Stanley, Laurel et Jefferson. Stan Laurel Stan Laurel vers 1920 Données clés Nom de naissance Arthur Stanley Jefferson Naissance 16 juin 1890Ulverston, Angleterre(Royaume-Uni) Nationalité Britannique Décès 23 février 1965 (à 74 ans)Santa Monica (États-Unis) Profession Acteur Films notables Laurel et Hardy conscrits (1939) modifier Arthur Stanley Jefferson, dit Stan Laurel, né le 16 juin 1890 à Ulverston, Lancashire dans le nord de l'Angleterre...

Federico Allasio

Questa voce o sezione sull'argomento calciatori è priva o carente di note e riferimenti bibliografici puntuali. Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento. Federico Allasio Nazionalità Italia ...

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

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

Cheshire West and Chester

Cet article est une ébauche concernant l’Angleterre. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Cheshire West and Chester Administration Pays Royaume-Uni Comté Cheshire Chef-lieu Chester Démographie Population 332 210 hab. (2014) Densité 362 hab./km2 Rang 19e / 326 Géographie Coordonnées 53° 12′ 47″ nord, 2° 54′ 07″ ouest Superficie 91 670&...

Reconstruction era

Military occupation of southern US states from 1865 to 1877 This article is about the history of the United States from 1865 until 1877. For the U.S. legislation enacted between 1867 and 1868, see Reconstruction Acts. For other uses, see Reconstruction (disambiguation). Reconstruction era1865–1877From left to right and up to the bottom: The ruins of Richmond, Virginia; newly-freed African Americans voting for the first time in 1867;[1] office of the Freedmen's Bureau in Memphis, Ten...

Condor (attraction)

Pour les articles homonymes, voir Condor. Condor à Phantasialand. Condor est le nom d'un modèle de manège fabriqué par Huss Park Attractions. Principe et fonctionnement L'attraction est composée d'un mât sur lequel un élément mobile monte et descend. Il effectue également une rotation autour de ce mat. Cet élément est composé de 4 bras supportant chacun une roue à l'horizontale qui peut faire une rotation dans les deux sens et qui est équipée elle-même sur son pourtour d...

United States at the Olympics

See also: United States at the Summer Olympics and United States at the Winter Olympics Sporting event delegationUnited States at theOlympicsFlag of the United StatesIOC codeUSANOCUnited States Olympic & Paralympic CommitteeWebsitewww.teamusa.orgMedalsRanked 1st Gold 1,179 Silver 956 Bronze 833 Total 2,968 Summer appearances189619001904190819121920192419281932193619481952195619601964196819721976198019841988199219962000200420082012201620202024Winter appearances19241928193219361948195219561...

متحف السيارات التاريخية والقديمة والتقليدية

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. مدينة متحف السيارات هو متحف للسيارات الكلاسيكية والفخمة والقديمة في منطقة الشويخ الصناعية في دولة الكويت.[1][2] افتتح المبنى في 10 أكتوبر عام 2010، ويتألف من منطقتين، منط...

Inchicore railway works

Ireland's major rail engineering facility, in Dublin Inchicore Railway WorksTrain passing Inchicore railway works in 1975OperatedSince 1846 (1846)[1]LocationInchicore, Dublin, IrelandCoordinates53°20′25″N 6°19′39″W / 53.3403°N 6.3274°W / 53.3403; -6.3274IndustryRail transportArea73 acres (30 ha)[1]Owner(s)GS&WR (1844-1924)Great Southern (1925-1944)CIÉ (1945-1987)Irish Rail (1987-present) Armoured train at Inchicore Works 1922 ...

Fuk Loi Estate

Public housing estate in Tsuen Wan, Hong Kong Fuk Loi EstateFuk Loi EstateGeneral informationLocation55 Hoi Pa Street, Tsuen WanNew Territories, Hong KongCoordinates22°22′26″N 114°06′48″E / 22.37381°N 114.11332°E / 22.37381; 114.11332StatusCompletedCategoryPublic rental housingPopulation6,999[1] (2016)No. of blocks9[2]No. of units3,100[2]ConstructionConstructed1963; 61 years ago (1963)AuthorityHong Kong Housing...

Susan Anspach

American actress (1942–2018) Susan AnspachAnspach in 1979BornSusan Florence Anspach(1942-11-23)November 23, 1942New York City, New York U.S.DiedApril 2, 2018(2018-04-02) (aged 75)Los Angeles, California, U.S.OccupationActressYears active1964–2011Spouses Mark Goddard (m. 1970; div. 1978) Sherwood Ball (m. 1982; div. 1988) Children2 Susan Florence Anspach (ONS-bok ; November 23,...

Richard Anschütz

German chemist (1852–1937) Richard AnschützBorn(1852-03-10)10 March 1852Darmstadt, German ConfederationDied8 January 1937(1937-01-08) (aged 84)Darmstadt, Germany[1]NationalityGermanAlma materUniversity of BonnScientific careerInstitutionsUniversity of BonnDoctoral advisorAugust KekuléDoctoral studentsHans Meerwein Carl Johann Philipp Noé Richard Anschütz FRSE (Hon) (10 March 1852 – 8 January 1937) was a German organic chemist.[1] Anschütz received his PhD at...

Guerre terrestre

La guerre terrestre ou combat terrestre est un type d'opérations militaires dans lesquelles le combat a principalement lieu dans un champ de bataille situé sur la surface terrestre, contrairement à la guerre navale ou la guerre aérienne. La guerre terrestre se caractérise par l'emploi d'un nombre important de soldats mettant en œuvre une diversité de compétences, méthodes de combat et équipements. Elle peut être menée sur des terrains et environnements météorologiques variés al...

Club Atlético Huracán

Disambiguazione – Se stai cercando altre squadre con nome simile, vedi Huracan (disambigua). Club Atlético HuracánCalcio El Globo (La Mongolfiera), Los Quemeros (I piromani) Segni distintiviUniformi di gara Casa Trasferta Terza divisa Colori sociali Bianco, rosso SimboliMongolfiera Dati societariCittàBuenos Aires Nazione Argentina ConfederazioneCONMEBOL Federazione AFA CampionatoPrimera División Fondazione1908 Presidente David Garzón Allenatore Facundo Sava StadioTomás Adolfo Du...

Troubadour

Pour l’article homonyme, voir Troubadour (homonymie). Bernart de Ventadorn, troubadour médiéval occitan - manuscrit de musique troubadour du XIIIe siècle. Un troubadour (de l'occitan trobador, trobairitz au féminin : « trouveur », « trouveuse » au féminin) est un compositeur, poète, et musicien médiéval de langue d'oc qui interprétait ou faisait interpréter ses œuvres poétiques par des jongleurs ou des ménestrels. Les femmes qui pratiquent l'a...

/profillengkap.com/index.php/article/Michael Hüther

Deaimon

Bente, Mandah, Indragiri Hilir

Browser user interface

C9 Entertainment

Drew County, Arkansas

13 November

Saint-Sébastien (Creuse)

Angela Jankulovska

146th Infantry Brigade (United Kingdom)

North-West (European Parliament constituency)

Nestlé Wyeth Nutrition