Glosar de teoria graficelor - Glossary of graph theory

Acesta este un glosar al teoriei graficelor . Teoria graficelor este studiul graficelor , sistemelor de noduri sau vârfuri conectate în perechi prin linii sau muchii .

Simboluri

Paranteza patrata [ ]: $G [S]$ este subgraful unui grafic $G$ pentru vertex submulțime $S$ .
Simbolul principal ': Prim simbol este adesea folosit pentru a modifica notația pentru invarianti grafic , astfel încât acesta se aplică graficului liniar în locul graficului dat. De exemplu, $α (G)$ este numărul de independență al unui grafic; $α' (G)$ este numărul corespunzător al graficului, care este egal cu numărul de independență al graficului său liniar. În mod similar, $χ (G)$ este numărul cromatic al unui grafic; $χ' (G)$ este indicele cromatic al graficului, care este egal cu numărul cromatic al graficului său liniar.

A

absorbant: Un set absorbant al unui grafic direcționat este un set de vârfuri astfel încât, pentru orice vârf , există o margine dinspre un vârf de . ${\ displaystyle A}$ ${\ displaystyle G}$ ${\ displaystyle v \ în G \ setminus A}$ ${\ displaystyle v}$ ${\ displaystyle A}$
acromatic: Numărul acromatic al unui grafic este numărul maxim de culori dintr-o colorare completă.
aciclic: 1. Un grafic este aciclic dacă nu are cicluri. Un grafic aciclic nedirecționat este același lucru cu o pădure . Grafele aciclice direcționate se numesc mai rar grafuri aciclice direcționate.; 2. O colorare aciclică a unui grafic nedirectat este o colorare adecvată în care la fiecare două clase de culoare induce o pădure.
matricea de adiacență: Matricea de adiacenta a unui grafic este o matrice ale cărei rânduri și coloane sunt ambele indexate de noduri ale grafului, cu unul din celulă pentru rândul $i$ și coloana $j$ atunci când nodurile $i$ și $j$ sunt adiacente, și un zero altfel.
adiacent: 1. Relația dintre două vârfuri care sunt ambele puncte finale ale aceleiași margini.; 2. Relația dintre două muchii distincte care împart un vârf final.
α: Pentru un grafic $G$ , $α (G)$ (folosind litera greacă alpha) este numărul său de independență (a se vedea independent ), iar $α' (G)$ este numărul său de potrivire (a se vedea potrivirea ).
alternativ: Într-un grafic cu o potrivire, o cale alternativă este o cale ale cărei margini alternează între marginile potrivite și cele neegalate. Un ciclu alternativ este, în mod similar, un ciclu ale cărui margini alternează între muchiile potrivite și cele neegalate. O cale de mărire este o cale alternativă care începe și se termină la vârfurile nesaturate. O potrivire mai mare poate fi găsită ca diferență simetrică de potrivire și cale de mărire; o potrivire este maximă dacă și numai dacă nu are o cale de mărire.
anticaten: Într-un grafic aciclic direcționat , un subset $S$ de vârfuri care sunt perechi incomparabile, adică pentru oricare din $S$ , nu există o cale direcționată de la $x$ la $y$ sau de la $y$ la $x$ . Inspirat de noțiunea de anticatenuri în seturi parțial ordonate . ${\ displaystyle x \ leq y}$
anti-margine: Sinonim pentru non-edge , o pereche de vârfuri neadiacente.
anti-triunghi: Un set independent cu trei vârfuri, complementul unui triunghi.
apex: 1. Un grafic de vârf este un grafic în care un vârf poate fi îndepărtat, lăsând un subgraf plan. Vârful îndepărtat se numește vârf. Un grafic $k$ -apex este un grafic care poate fi făcut plan prin eliminarea $k$ vârfurilor.; 2. Sinonim pentru vârf universal , un vârf adiacent tuturor celorlalte vârfuri.
arborescenţă: Sinonim pentru un copac înrădăcinat și dirijat; vezi copac .
arc: Vezi marginea .
săgeată: O pereche ordonată de vârfuri , cum ar fi o margine într-un grafic direcționat . O săgeată $(x, y)$ are o coadă $x$ , un cap $y$ și o direcție de $la x la y$ ; $y$ este declarat a fi succesorul direct la $x$ și $x$ predecesorul directă la $y$ . Săgeata $(y, x)$ este săgeata inversată a săgeții $(x, y)$ .
punct de articulare: Un vârf într-un grafic conectat a cărui eliminare ar deconecta graficul.
-ary: Un copac $k$ -ary este un copac înrădăcinat în care fiecare vârf intern nu are mai mult de $k$ copii. Un copac 1-ari este doar o cale. Un copac cu 2 arii este, de asemenea, numit arbore binar , deși acest termen se referă mai corect la copacii cu 2 arii în care copiii fiecărui nod se disting ca fiind copii stângi sau dreapta (cu cel mult unul din fiecare tip). Se spune că un copac $k$ -ary este complet dacă fiecare vârf intern are exact $k$ copii.
mărind: Un tip special de cale alternativă; vezi alternativ .
automorfism: Un automorfism grafic este o simetrie a unui grafic, un izomorfism de la grafic la sine.

B

sac: Unul dintre seturile de vârfuri dintr-o descompunere a copacului .
echilibrat: Un grafic bipartit sau multipartit este echilibrat dacă fiecare două subseturi ale partiției sale de vârf au dimensiuni una în alta.
lățime de bandă: Lățimii de bandă a unui grafic $G$ este minim, peste toate ordonări de noduri de $G$ , din lungimea cea mai lungă latură (numărul de pași în ordonarea între cele două obiective sale). De asemenea, este cu unul mai mic decât dimensiunea clicii maxime într-un interval corect de finalizare a lui $G$ , ales pentru a minimiza dimensiunea clicei.
biclique: Sinonim pentru grafic bipartit complet sau subgraf bipartit complet; vezi complet .
biconectat: De obicei, un sinonim pentru $2$ -vertex-conectat , dar uneori include K _2, deși nu este 2-conectat. Vezi conectat ; pentru componente biconectate , a se vedea componenta .
numărul de legătură: Cel mai mic raport posibil dintre numărul vecinilor unui subgrup corespunzător de vârfuri și dimensiunea subgrupului.
bipartit: Un grafic bipartit este un grafic ale cărui vârfuri pot fi împărțite în două seturi disjuncte astfel încât vârfurile dintr-un set nu sunt conectate între ele, dar pot fi conectate la vârfurile din celălalt set. Altfel spus, un grafic bipartit este un grafic fără cicluri impare; în mod echivalent, este un grafic care poate fi corect colorat cu două culori. Graficele bipartite sunt adesea scrise $G = (U, V, E)$ unde $U$ și $V$ sunt subseturile de vârfuri ale fiecărei culori. Cu toate acestea, cu excepția cazului în care graficul este conectat, este posibil să nu aibă o culoare unică 2.
biregular: Un grafic biregular este un grafic bipartit în care există doar două grade de vârf diferite, câte unul pentru fiecare set de bipartiție de vârf.
bloc: 1. Un bloc al unui grafic $G$ este un subgraf maxim care este fie un vârf izolat, o margine de punte, fie un subgraf cu 2 conexiuni. Dacă un bloc este 2-conectat, fiecare pereche de vârfuri din el aparține unui ciclu comun. Fiecare margine a unui grafic aparține exact unui bloc.; 2. Graficul bloc al unui grafic $G$ este un alt grafic ale cărui vârfuri sunt blocurile lui $G$ , cu o margine care leagă două vârfuri atunci când blocurile corespunzătoare au un punct de articulație; adică, este intersecția graficul blocurilor de $G$ . Graficul bloc al oricărui grafic este o pădure .; 3. Bloc-cut (sau bloc-cutpoint) Graficul unui grafic $G$ este un graf bipartit în care un set este format din partite cut vîrfurile $G$ , iar celălalt are un nod pentru fiecare bloc de $G$ . Când $G$ este conectat, graficul punctului de blocare este un arbore. ${\ displaystyle b_ {i}}$ ${\ displaystyle B_ {i}}$; 4. Un grafic de blocuri (numit și arborele unei clici dacă este conectat și uneori denumit în mod eronat un arbore Husimi) este un grafic al cărui blocuri sunt grafice complete. O pădure este un grafic bloc; deci, în special, graficul bloc al oricărui grafic este un grafic bloc și fiecare grafic bloc poate fi construit ca grafic bloc al unui grafic.
legătură: Un set minim de tăiere : un set de muchii a căror eliminare deconectează graficul, pentru care niciun subset adecvat nu are aceeași proprietate.
carte: 1. O carte , un grafic de carte sau o carte triunghiulară este un grafic tripartit complet $K 1,1, n$ ; o colecție de $n$ triunghiuri unite la o margine comună.; 2. Un alt tip de grafic, numit și carte sau carte patrulateră, este o colecție de $4$ -cicluri unite la o margine comună; produsul cartezian al unei stele cu margine.; 3. O încorporare de carte este încorporarea unui grafic într-o carte topologică, un spațiu format prin alăturarea unei colecții de semiplane de-a lungul unei linii comune. De obicei, vârfurile încorporării trebuie să fie pe linie, care se numește coloana vertebrală a încastrării, iar marginile încastrării trebuie să se afle într-un singur semiplan, una dintre paginile cărții.
mărăcine: O mărăcină este o colecție de subgrafe conectate care se ating reciproc, în care două subgrafe se ating dacă au un vârf sau fiecare include un punct final al unei margini. Ordinea unei mărăcini este cea mai mică dimensiune a unui set de vârfuri care are o intersecție fără gol cu toate subgrafele. Lățimea copacului unui grafic este ordinea maximă a oricăruia dintre mărăcini.
ramură-descompunere: O ramură-descompunere a $G$ este o grupare ierarhică a marginilor $G$ , reprezentate de un arbore binar nerădăcinoși cu frunzele sale etichetate de marginile $G$ . Lățimea unei ramificări-descompunere este maximă, peste marginile $e$ ale acestui arbore binar, a numărului de vârfuri partajate între subgrafe determinate de marginile lui $G$ în cele două subarburi separate de $e$ . Branchwidth de $G$ este lățimea minimă a oricărei ramificație de descompunere a $G$ .
lățime de ramură: Vezi descompunerea ramurilor .
pod: 1. Un pod , istm sau margine tăiată este o margine a cărei îndepărtare ar deconecta graficul. Un grafic fără punte este cel care nu are punți; echivalent, un grafic cu 2 margini.; 2. Mai ales în contextul testării planarității , o punte a unui ciclu este un subgraf maxim care este disjunct de ciclu și în care fiecare două margini aparțin unei căi care este disjunsă intern de ciclu. Un acord este un pod cu o singură margine. Un ciclu periferic este un ciclu cu cel mult un pod; trebuie să fie o față în orice încorporare plană a graficului său.; 3. O punte a unui ciclu poate însemna și o cale care leagă două vârfuri ale unui ciclu, dar este mai scurtă decât oricare dintre căile din ciclu care leagă aceleași două vârfuri. Un grafic în punte este un grafic în care fiecare ciclu de patru sau mai multe vârfuri are o punte.
fără punte: Un grafic fără punte este un grafic care nu are margini de punte; adică un grafic cu 2 margini .
fluture: 1. Graficul fluture are cinci vârfuri și șase margini; este format din două triunghiuri care împart un vârf.; 2. Rețeaua fluture este un grafic utilizat ca arhitectură de rețea în calcul distribuit, strâns legat de ciclurile conectate la cub .

C

C: $C n$ este ungrafic ciclu $n$ -vertex; vezi ciclul .
cactus: Un grafic cactus , copac cactus, cactus sau copac Husimi este un grafic conectat în care fiecare margine aparține cel mult unui ciclu. Blocurile sale sunt cicluri sau margini simple. Dacă, în plus, fiecare vârf aparține cel mult două blocuri, atunci se numește cactus de Crăciun.
cuşcă: O cușcă este un grafic obișnuit cu cea mai mică ordine posibilă pentru circumferința sa.
canonic
canonizare: O formă canonică a unui grafic este un invariant astfel încât două grafice au invarianți egali dacă și numai dacă sunt izomorfi. Formele canonice pot fi, de asemenea, numite invarianți canonici sau invarianți complet și, uneori, sunt definite numai pentru graficele dintr-o anumită familie de grafice. Canonizarea grafică este procesul de calcul al unei forme canonice.
card: Un grafic format dintr-un grafic dat prin ștergerea unui vârf, în special în contextul conjecturii de reconstrucție . A se vedea, de asemenea , pachetul , multiset-ul tuturor cărților unui grafic.
lățimea de sculptură: Lățimea de sculptură este o noțiune de lățime a graficului analogă cu lățimea de ramură, dar folosind grupări ierarhice de vârfuri în loc de grupări ierarhice de margini.
omida: Un copac omidă sau omidă este un copac în care nodurile interne induc o cale.
centru: Centrul unui grafic este setul de noduri de minim excentricitate .
lanţ: 1. Sinonim pentru mers .; 2. Atunci când se aplică metode de la topologia algebrică la grafice, un element al unui complex de lanț , și anume un set de vârfuri sau un set de margini.
Constanta Cheeger: Vezi extinderea .
cireașă: O cireșă este o cale pe trei vârfuri.
χ: $χ (G)$ (folosind litera greacă chi) este numărul cromatic al lui $G$ și $χ' (G)$ este indicele său cromatic; vezi cromatic și colorant .
copil: Într-un copac înrădăcinat, un copil al unui vârf $v$ este vecin cu $v de$ -a lungul unei margini de ieșire, una care este îndreptată departe de rădăcină.
coardă
chordal: 1. Un acord al unui ciclu este o margine care nu aparține ciclului, pentru care ambele puncte finale aparțin ciclului.; 2. Un grafic acordal este un grafic în care fiecare ciclu de patru sau mai multe vârfuri are o coardă, deci singurele cicluri induse sunt triunghiuri.; 3. Un grafic puternic acord este un grafic acord în care fiecare ciclu de lungime șase sau mai mult are o coardă impar.; 4. Un grafic bipartit acordal nu este acordal (decât dacă este o pădure); este un grafic bipartit în care fiecare ciclu de șase sau mai multe vârfuri are o coardă, deci singurele cicluri induse sunt 4 cicluri.; 5. Un acord al unui cerc este un segment de linie care leagă două puncte de pe cerc; Graficul intersecție dintr - o colecție de acorduri se numește un grafic cerc .
cromatic: Având de-a face cu colorarea; vezi culoarea . Teoria graficului cromatic este teoria colorării graficului. Numărul cromatic $χ (G)$ este numărul minim de culori necesare într - o colorare corespunzătoare a $G$ . $χ'(G)$ este indicele cromatic al $G$ , numărul minim de culori necesare într - o buna margine de colorat de $G$ .
de ales
alegerea: Un grafic este $k-$ poate fi ales dacă are o listă de colorat ori de câte ori fiecare vârf are o listă de $k$ culori disponibile. Alegerea graficului este cel mai mic $k$ pentru care este $k-$ selectabil.
cerc: Un grafic de cerc este graficul de intersecție a corzilor unui cerc.
circuit: Un circuit se poate referi la o pistă închisă sau la un element al spațiului ciclului (un subgraf eulerian care se întinde). Rangul de circuit al unui grafic este dimensiunea spațiului său ciclu.
circumferinţă: Circumferința unui grafic este lungimea celui mai lung ciclu de simplu. Graficul este hamiltonian dacă și numai dacă circumferința sa este egală cu ordinea sa.
clasă: 1. O clasă de grafice sau o familie de grafice este o colecție (de obicei infinită) de grafice, adesea definită ca graficele care au o anumită proprietate specifică. Cuvântul „clasă” este folosit mai degrabă decât „set” deoarece, cu excepția cazului în care se fac restricții speciale (cum ar fi restricționarea vârfurilor care trebuie trase dintr-un anumit set și definirea muchiilor pentru a fi seturi de două vârfuri) clasele de grafice nu sunt de obicei seturi când este formalizat folosind teoria mulțimilor.; 2. O clasă de culoare a unui grafic colorat este setul de vârfuri sau margini având o anumită culoare.; 3. În contextul teoremei lui Vizing , pe margini colorarea graficelor simple, se spune că un grafic este de clasa unu dacă indicele său cromatic este egal cu gradul său maxim, iar clasa a doua dacă indicele său cromatic este egal cu unu plus gradul. Conform teoremei lui Vizing, toate graficele simple sunt fie de clasa unu, fie de clasa a doua.
Gheară: O gheară este un copac cu un vârf intern și trei frunze, sau echivalent graficul bipartit complet $K 1,3$ . Un grafic fără gheare este un grafic care nu are un subgraf indus care este o gheară.
clică: O clică este un set de vârfuri adiacente reciproc (sau subgraful complet indus de acel set). Uneori, o clică este definită ca un set maxim de vârfuri adiacente reciproc (sau un subgraf complet maxim), unul care nu face parte dintr-un astfel de set (sau subgraf) mai mare. O $k-$ clică este o clică de ordinul $k$ . Numărul clicului $κ (G)$ al unui grafic $G$ este ordinea celei mai mari clici a acestuia. Un grafic de clică este un grafic de intersecție a clicurilor maxime. Vezi și biclique , un subgraf bipartit complet.
copac clica: Un sinonim pentru un grafic bloc .
lățime de clică: Clică lățimea unui grafic $G$ este numărul minim de etichete distincte necesare pentru a construi $G$ prin operații care creează un nod etichetat, formează unirea disjunctă a două grafice etichetate, se adaugă o muchie care leagă toate perechile de noduri cu etichete date sau reetichetat toate vârfurile cu o etichetă dată. Graficele lățimii clicului cel mult $2$ sunt exact graficele .
închis: 1. Un cartier închis este cel care include vârful său central; vezi cartierul .; 2. O plimbare închisă este una care începe și se termină la același vârf; vezi plimbare .; 3. Un grafic este închis tranzitiv dacă este egal cu închiderea sa tranzitivă; vezi tranzitiv .; 4. O proprietate de grafic este închisă sub o anumită operație pe grafice dacă, ori de câte ori argumentul sau argumentele operației au proprietatea, atunci la fel rezultatul. De exemplu, proprietățile ereditare sunt închise sub subgrafe induse; proprietățile monotone sunt închise sub subgrafe; iar proprietățile minore închise sunt închise sub minori.
închidere: 1. Pentru închiderea tranzitivă a unui grafic direcționat, consultați tranzitiv .; 2. O închidere a unui grafic direcționat este un set de vârfuri care nu au margini de ieșire la vârfurile din afara închiderii. De exemplu, o chiuvetă este o închidere cu un singur vârf. Problema închiderii este problema găsirii unei închideri cu greutate minimă sau maximă.
co-: Acest prefix are diverse semnificații care implică de obicei grafice complementare . De exemplu, un cograf este un grafic produs de operații care includ complementare; un cocoloring este un colorant în care fiecare induce vertex , fie un set independent (ca colorație corespunzătoare) sau o clică (ca într - un colorit al complementului).
culoare
colorare: 1. O colorare a graficului este o etichetare a vârfurilor unui grafic prin elemente dintr-un set dat de culori sau, în mod echivalent, o partiție a vârfurilor în subseturi, numite „clase de culori”, fiecare dintre acestea fiind asociat cu una dintre culori.; 2. Unii autori folosesc „colorare”, fără calificare, pentru a însemna o colorare adecvată, una care atribuie culori diferite punctelor finale ale fiecărei muchii. În colorarea graficelor, scopul este de a găsi o colorare adecvată care să utilizeze cât mai puține culori posibil; de exemplu, graficele bipartite sunt graficele care au coloranți cu doar două culori, iar teorema celor patru culori afirmă că fiecare grafic plan poate fi colorat cu cel mult patru culori. Se spune că un grafic este colorat $k$ dacă a fost (corect) colorat cu $k$ culori și $k-$ colorabil sau $k-$ cromatic dacă acest lucru este posibil.; 3. Au fost studiate multe variante de colorare, inclusiv colorarea muchiilor (marginile de colorare astfel încât să nu existe două margini cu același punct final să aibă o culoare), colorarea listei (colorarea corespunzătoare cu fiecare vârf limitată la un subset de culori disponibile), colorarea aciclică (fiecare subgraf cu două culori este aciclic), co-colorare (fiecare clasă de culoare induce un set independent sau o clică), colorare completă (la fiecare două clase de culori au o margine) și colorare totală (ambele margini și vârfuri sunt colorate).; 4. Numărul de colorare al unui grafic este unul plus degenerescența . Se numește așa deoarece aplicarea unui algoritm de colorat lacom unei ordonări de degenerare a graficului folosește cel mult aceste culori.
comparabilitate: Un grafic nedirecționat este un grafic de comparabilitate dacă vârfurile sale sunt elementele unui set parțial ordonat și două vârfuri sunt adiacente atunci când sunt comparabile în ordinea parțială. În mod echivalent, un grafic de comparabilitate este un grafic care are o orientare tranzitivă. Multe alte clase de grafice pot fi definite ca grafice de comparabilitate a tipurilor speciale de ordine parțială.
completa: Graficul complementul unui grafic simplu $G$ este un alt grafic pe același set vârfuri ca $G$ , cu o margine pentru fiecare două vârfuri care nu sunt adiacente în $G$ . ${\ displaystyle {\ bar {G}}}$
complet: 1. Un grafic complet este unul în care fiecare două vârfuri sunt adiacente: sunt prezente toate muchiile care ar putea exista. Un grafic complet cu $n$ vârfuri este adesea notat $K n$ . Un grafic bipartit complet este unul în care fiecare două vârfuri de pe laturile opuse ale partiției vârfurilor sunt adiacente. Un grafic complet bipartit cu $un$ noduri pe de o parte a peretelui despărțitor și $b$ nodurile de pe cealaltă parte este adesea notată $K a, b$ . Aceeași terminologie și notație a fost, de asemenea, extinsă pentru a completa grafice multipartite , grafice în care vârfurile sunt împărțite în mai mult de două subseturi și fiecare pereche de vârfuri din subseturi diferite sunt adiacente; în cazul în care numărul de noduri din subseturi sunt $o, b, c, ...$ atunci acest grafic este notat $K a, b, c, ...$ .; 2. Completarea unui grafic dat este un supergraf care are unele proprietăți dorite. De exemplu, o completare acordală este un supergraf care este un grafic acordal.; 3. O potrivire completă este un sinonim pentru o potrivire perfectă ; vezi potrivire .; 4. O colorare completă este o colorare adecvată în care fiecare pereche de culori este utilizată pentru punctele finale ale cel puțin unei margini. Fiecare colorare cu un număr minim de culori este completă, dar pot exista colorări complete cu un număr mai mare de culori. Numărul acromatic al unui grafic este numărul maxim de culori dintr-o colorare completă.; 5. Un invariant complet al unui grafic este un sinonim pentru o formă canonică, un invariant care are valori diferite pentru graficele neizomorfe.
componentă: O componentă conectată a unui grafic este un subgraf maxim conectat. Termenul este de asemenea utilizat pentru subgrafurilor maximale sau subseturi de noduri unui grafic de care au o ordine mai mare de conectivitate, inclusiv componente biconnected , componente triconnected și componente puternic conectate .
condensare: Condensarea unui graf orientat $G$ este un grafic aciclic direcționat cu un singur nod pentru fiecare componentă puternic legată de $G$ , și o margine de conectare perechi de componente care conțin cele două obiective de cel puțin o muchie în $G$ .
con: Un grafic care conține un vârf universal .
conectați: Cauza pentru a fi conectat .
conectat: Un grafic conectat este unul în care fiecare pereche de vârfuri formează punctele finale ale unei căi. Formele superioare de conectivitate includ conectivitate puternică în grafice direcționate (pentru fiecare două vârfuri există căi de la una la cealaltă în ambele direcții), grafice $k$ -cu vertex (eliminarea mai puțin de $k$ vârfuri nu poate deconecta graficul) și $k$ -edge -grafele conectate (eliminarea mai puțin de $k$ margini nu poate deconecta graficul).
conversa: Graficul invers este un sinonim pentru graficul de transpunere; vezi transpune .
nucleu: 1. Un $k$ -core este subgraful indus format prin eliminarea tuturor vârfurilor de grad mai mici decât $k$ și a tuturor vârfurilor al căror grad devine mai mic decât $k$ după îndepărtări anterioare. Vezi degenerescența .; 2. Un nucleu este un grafic $G$ astfel încât fiecare omomorfism grafic de la $G$ la sine este un izomorfism.; 3. Nucleul unui grafic $G$ este un grafic minim $H$ astfel încât să existe omomorfisme de la $G$ la $H$ și invers. $H$ este unic până la izomorfism. Poate fi reprezentat ca un subgraf indus de $G$ și este un nucleu în sensul că toate auto-omomorfismele sale sunt izomorfisme.; 4. În teoria potrivirilor grafice, nucleul unui grafic este un aspect al descompunerii sale Dulmage-Mendelsohn , format ca unire a tuturor potrivirilor maxime.
cotree: 1. Complementul unui copac întins .; 2. O structură de copac înrădăcinată utilizată pentru a descrie un cograf , în care fiecare vârf al cografului este o frunză a arborelui, fiecare nod intern al arborelui este etichetat cu 0 sau 1 și doi vârfuri ale cografului sunt adiacente dacă și numai dacă sunt cele mai mici comune strămoșul din copac este etichetat 1.
acoperi: Un capac de vârf este un set de vârfuri incidente la fiecare margine dintr-un grafic. Un capac de margine este un set de margini incidente fiecărui vârf dintr-un grafic. Un set de subgrafe ale unui grafic acoperă acel grafic dacă unirea sa - luată la vârf și la margine - este egală cu graficul.
critic: Un grafic critic pentru o proprietate dată este un grafic care are proprietatea, dar astfel încât fiecare subgraf format prin ștergerea unui singur vârf nu are proprietatea. De exemplu, un grafic critic este unul care are o potrivire perfectă (un factor 1) pentru fiecare ștergere a vârfurilor, dar (deoarece are un număr impar de vârfuri) nu are o potrivire perfectă. Comparați hipo- , utilizat pentru grafice care nu au o proprietate, dar pentru care fiecare ștergere cu un singur vârf are.
cub
cub: 1. Graficul cubului , graficul cu opt vârfuri al vârfurilor și marginilor unui cub.; 2. Graficul hipercub , o generalizare mai înaltă a graficului cubului.; 3. Grafic cub pliat , format dintr-un hipercub prin adăugarea unei potriviri de conectare la vârfuri opuse.; 4. Graficul cubului înjumătățit , jumătatea pătratului unui grafic hipercub.; 5. Cub parțial , un subgraf de conservare a distanței unui hipercub.; 6. Cubul unui grafic $G$ este puterea graficului $G 3$ .; 7. Grafic cub , un alt nume pentru un grafic $3$ -regular, unul în care fiecare vârf are trei muchii incidente.; 8. Cicluri conectate la cub , un grafic cub format prin înlocuirea fiecărui vârf al unui hipercub cu un ciclu.
a tăia
cut-set: O tăietură este o partiție a vârfurilor unui grafic în două subseturi sau setul (cunoscut și sub denumirea de set de tăieturi) de margini care se întind pe o astfel de partiție, dacă setul respectiv nu este gol. Se spune că o margine acoperă partiția dacă are puncte finale în ambele subseturi. Astfel, eliminarea unui set de tăieturi dintr-un grafic conectat îl deconectează.
punct de tăiere: Vezi punctul de articulare .
tăiați spațiul: Spațiul tăiat al unui grafic este un GF (2) - spațiu vectorial având setul tăiat s al graficului ca elemente și diferența simetrică a mulțimilor ca operație de adunare vectorială.
ciclu: Un ciclu se poate referi fie la o plimbare închisă (numită și tur ), fie mai precis la o plimbare închisă fără vârfuri repetate și, în consecință, margini (numită și ciclul simplu). În ambele cazuri, alegerea primului vârf este considerată de obicei lipsită de importanță: permutațiile ciclice ale mersului produc același ciclu. Cazuri speciale importante de cicluri includ cicluri hamiltoniene , cicluri induse , cicluri periferice , și cel mai scurt ciclu, care definește circumferința unui grafic. Un $k-$ ciclu este un ciclu de lungime $k$ ; de exemplu un $2-$ ciclu este un digon și un $3-$ ciclu este un triunghi. Un grafic de ciclu este un grafic care este el însuși un ciclu simplu; un grafic de ciclu cu $n$ vârfuri este notat în mod obișnuit $C n$ . Spațiul ciclului este un spațiu vectorial generat de cicluri simple într-un grafic.

D

DAG: Abreviere pentru graficul aciclic direcționat , un grafic direcționat fără cicluri direcționate.
punte: Multisetul de grafuri format dintr-un singur grafic $G$ prin ștergerea unui singur vârf în toate modurile posibile, în special în contextul conjecturii de reconstrucție . O punte de margine este formată în același mod prin ștergerea unei singure margini în toate modurile posibile. Graficele dintr-un pachet se mai numesc și cărți . A se vedea, de asemenea, critice (grafice care au o proprietate care nu este deținută de nicio carte) și hipo- (grafice care nu au o proprietate care este deținută de toate cărțile).
descompunere: Vezi descompunerea copacilor , descompunerea căii sau descompunerea ramurilor .
degenerat
degenerare: Un grafic $k-$ degenerat este un grafic nedirecționat în care fiecare subgraf indus are grad minim cel mult $k$ . Degenerării unui grafic este cel mai mic $k$ pentru care este $k$ -degenerate. O ordonare a degenerării este o ordonare a vârfurilor astfel încât fiecare vârf să aibă un grad minim în subgraful indus al acestuia și în toate vârfurile ulterioare; într-o ordonare de degenerare a unui grafic $k-$ degenerat, fiecare vârf are cel mult $k$ vecini mai târziu. Degenerarea este, de asemenea, cunoscută sub numele de numărul $k$ -core, lățimea și legătura, iar unul plus degenerescența se mai numesc și numărul de colorare sau numărul Szekeres – Wilf. $k-$ grafele degenerate au fost numite și $k-$ grafice inductive.
grad: 1. Gradul unui vârf într-un grafic este numărul său de muchii incidente. Gradul unui grafic $G$ (sau gradul său maxim) este maximul gradelor vârfurilor sale, deseori notate $Δ (G)$ ; gradul minim al lui $G$ este minimul gradelor sale de vârf, deseori notate $δ (G)$ . Gradul este uneori numit valență ; gradul de $v$ în $G$ poate fi notat $d G (v)$ , $d (G)$ sau $deg (v)$ . Gradul total este suma gradelor tuturor vârfurilor; prin lema de strângere de mână este un număr par. Secvența de studii este colecția de grade de toate nodurile, pentru sortat de la cel mai mare la cel mai mic. Într-un grafic direcționat, se pot distinge gradul de intrare (numărul de muchii de intrare) și gradul de ieșire (numărul de muchii de ieșire).; 2. Gradul de omomorfism al unui grafic este un sinonim pentru numărul lui Hadwiger , ordinea celui mai mare clice minor.
Δ, δ: $Δ (G)$ (folosind litera greacă delta) este gradul maxim al unui vârf în $G$ , iar $δ (G)$ este gradul minim; vezi gradul .
densitate: Într-un grafic de n noduri, densitatea este raportul dintre numărul de muchii al graficului și numărul de muchii dintr-un grafic complet pe n noduri. Vezi graficul dens .
adâncime: Adâncimea unui nod dintr-un copac înrădăcinat este numărul de margini din calea de la rădăcină la nod. De exemplu, adâncimea rădăcinii este 0 și adâncimea oricăruia dintre nodurile sale adiacente este 1. Este nivelul unui nod minus unul. Rețineți, totuși, că unii autori folosesc în schimb profunzimea ca sinonim pentru nivelul unui nod.
diametru: Diametrul unui grafic conectat este lungimea maximă a unei căi mai scurte . Adică, este maximul distanțelor dintre perechile de vârfuri din grafic. Dacă graficul are greutăți pe margini, atunci diametrul său ponderat măsoară lungimea căii cu suma greutăților marginii de-a lungul unei căi, în timp ce diametrul neponderat măsoară lungimea căii cu numărul de margini. Pentru graficele deconectate, definițiile variază: diametrul poate fi definit ca infinit sau ca cel mai mare diametru al unei componente conectate sau poate fi nedefinit.
diamant: Graficul diamant este un grafic neorientat cu patru noduri și cinci muchii.
deconectat: Puternic ly conectat . (Nu trebuie confundat cu deconectat )
digon: Un digon este un ciclu simplu de lungime două într-un grafic direcționat sau un multigraf. Digonii nu pot apărea în grafice nedirecționate simple, deoarece necesită repetarea aceleiași margini de două ori, ceea ce încalcă definiția simplului .
digraf: Sinonim pentru grafic dirijat .
dipath: Vezi calea îndreptată .
predecesor direct: Coada unei margini direcționate al cărei cap este vârful dat.
succesor direct: Capul unei margini direcționate a cărei coadă este vârful dat.
regizat: Un grafic direcționat este unul în care marginile au o direcție distinctă, de la un vârf la altul. Într-un grafic mixt , o margine direcționată este din nou una care are o direcție distinctă; muchiile direcționate pot fi numite și arce sau săgeți.
arc dirijat: Vezi săgeata .
margine îndreptată: Vezi săgeata .
linie dirijată: Vezi săgeata .
cale îndreptată: O cale în care toate margine s au aceeași direcție . Dacă o cale direcționată duce de la vârful $x$ la vârful $y$ , $x$ este predecesorul lui $y$ , $y$ este succesorul lui $x$ și se spune că $y$ este accesibil din $x$ .
direcţie: 1. Relația asimetrică dintre două vârfuri adiacente într-un grafic , reprezentate ca o săgeată .; 2. Relația asimetrică dintre două vârfuri pe o cale direcționată .
Deconectat: Cauza pentru a fi deconectat .
deconectat: Nu este conectat .
disjunct: 1. Două subgrafe sunt margini disjuncte dacă nu au margini și vertic disjunct dacă nu au vârfuri.; 2. Unirea separată a două sau mai multe grafice este un grafic ale cărui seturi de vârf și margini sunt uniunile disjuncte ale mulțimilor corespunzătoare.
distanţă: Distanța dintre oricare două noduri într - un grafic este lungimea cea mai scurtă cale cu cele două vârfuri ca obiective sale.
domatic: O partiție domatică a unui grafic este o partiție a vârfurilor în seturi dominante. Numărul domatic al graficului este numărul maxim de seturi dominante într-o astfel de partiție.
dominatoare: Un set dominant este un set de vârfuri care include sau este adiacent fiecărui vârf din grafic; nu trebuie confundat cu un capac de vârf, un set de vârfuri care este incident la toate muchiile din grafic. Tipuri speciale importante de seturi dominante includ seturi dominante independente (seturi dominante care sunt și seturi independente) și seturi dominante conectate (seturi dominante care au indus subgrafe conectate). Un set care domină un singur vârf poate fi numit și vârf universal. Numărul de dominație al unui grafic este numărul de vârfuri din cel mai mic set dominant.

E

E: $E (G)$ este setul de margini al lui $G$ ; vezi setul de margini .
ureche: O ureche a unui grafic este o cale ale cărei puncte finale pot coincide, dar în care altfel nu există repetări de vârfuri sau margini.
descompunerea urechii: O descompunere a urechii este o partiție a marginilor unui grafic într-o succesiune de urechi, fiecare dintre ale cărui puncte finale (după primul) aparțin unei urechi anterioare și fiecare dintre ale cărui puncte interioare nu aparțin niciunei urechi anterioare. O ureche deschisă este o cale simplă (o ureche fără vârfuri repetate), iar o descompunere a urechii deschise este o descompunere a urechii în care fiecare ureche după prima este deschisă; un grafic are o descompunere a urechii deschise dacă și numai dacă este biconectat. O ureche este impară dacă are un număr impar de margini, iar o descompunere a urechii impare este o descompunere a urechii în care fiecare ureche este impară; un grafic are o descompunere ciudată a urechii dacă și numai dacă este factor critic.
excentricitate: Excentricitatea unui vârf este cea mai îndepărtată distanță de la acesta la orice alt vârf.
margine: O muchie este (împreună cu vârfurile) una dintre cele două unități de bază din care sunt construite graficele. Fiecare margine are două (sau în hipergrafuri, mai mult) vârfuri de care este atașat, numite punctele sale finale. Marginile pot fi direcționate sau nedirecționate; muchiile nedirecționate se numesc și linii, iar marginile direcționate se mai numesc arce sau săgeți. Într-un grafic simplu neorientat , o margine poate fi reprezentată ca setul vârfurilor sale, iar într-un grafic simplu direcționat poate fi reprezentată ca o pereche ordonată a vârfurilor sale. O margine care leagă vârfurile $x$ și $y$ este uneori scrisă $xy$ .
tăietură de margine: Un set de margine și a cărui îndepărtare decuplează Graficul . O tăietură cu o singură margine se numește pod , istm sau margine tăiată .
set de margini: Ansamblul muchiilor unui grafic dat $G$ , uneori notat cu $E (G)$ .
grafic fără margini: Graficul tocit sau graficul interupt pe un anumit set de noduri este grafic care nu are margini. Uneori se numește graficul gol, dar acest termen se poate referi și la un grafic fără vârfuri.
încorporare: O încorporare a unui grafic este o reprezentare topologică a unui grafic ca subset al unui spațiu topologic cu fiecare vârf reprezentat ca un punct, fiecare margine reprezentată ca o curbă având punctele finale ale muchiei ca puncte finale ale curbei și fără alte intersecții între vârfuri sau margini. Un grafic plan este un grafic care are o astfel de încorporare în planul euclidian, iar un grafic toroidal este un grafic care are o astfel de încorporare pe un tor. De genul unui grafic este minim genul posibile ale unei bidimensional manifold pe care poate fi încorporat.
grafic gol: 1. Un grafic fără margini pe un set de vârfuri fără gol.; 2. Graficul de ordine zero , un grafic fără vârfuri și fără margini.
Sfârșit: Un sfârșit al unui grafic infinit este o clasă de echivalență a razelor, unde două raze sunt echivalente dacă există o a treia rază care include infinit multe vârfuri de la ambele.
punctul final: Unul dintre cele două vârfuri unite de o margine dată sau unul dintre primul sau ultimul vârf al unei plimbări, poteci sau poteci. Primul punct final al unei margini direcționate este numit coadă, iar al doilea punct final este numit cap .
enumerare: Enumerarea graficelor este problema numărării graficelor într-o clasă dată de grafice, în funcție de ordinea lor. Mai general, problemele de enumerare se pot referi fie la probleme de numărare a unei anumite clase de obiecte combinatorii (cum ar fi clici, seturi independente, coloranți sau copaci care se întind), fie de listare algoritmică a tuturor acestor obiecte.
Eulerian: O cale euleriană este o plimbare care folosește fiecare margine a unui grafic exact o dată. Un circuit eulerian (numit și ciclu eulerian sau tur Euler) este o plimbare închisă care folosește fiecare margine exact o dată. Un grafic eulerian este un grafic care are un circuit eulerian. Pentru un grafic nedirectat, aceasta înseamnă că graficul este conectat și fiecare vârf are un nivel egal. Pentru un grafic direcționat, aceasta înseamnă că graficul este puternic conectat și fiecare vârf are un grad egal cu gradul exterior. În unele cazuri, cerința de conectivitate este slăbită, iar un grafic care îndeplinește numai cerințele privind gradul este numit Eulerian.
chiar: Divizibil cu două; de exemplu, un ciclu egal este un ciclu a cărui lungime este uniformă.
expansor: Un grafic de expansiune este un grafic a cărui expansiune de margine, expansiune de vârf sau expansiune spectrală este delimitată de zero.
expansiune: 1. Extinderea marginii, numărul isoperimetric sau constanta Cheeger a unui grafic $G$ este raportul minim, peste subseturi $S$ de cel mult jumătate din nodurile $G$ , numărul de muchii care ies $S$ la numărul de noduri din $S$ .; 2. Expansiunea vârfului, numărul izoperimetric al vârfului sau mărirea unui grafic $G$ este raportul minim, pe subseturile $S$ de cel mult jumătate din vârfurile lui $G$ , ale numărului de vârfuri din exterior, dar adiacente lui $S$ față de numărul de vârfuri din $S$ .; 3. Extinderea vecin unic al unui grafic $G$ este raportul minim, peste subseturi de cel mult jumătate din nodurile $G$ , din numărul de noduri exterioare $S$ , dar în vecinătatea unui nod unic în $S$ la numărul de noduri din $S$ .; 4. Expansiunea spectrală a unui grafic $d$ -regular $G$ este decalajul spectral dintre cea mai mare valoare proprie $d$ a matricei sale de adiacență și a doua cea mai mare valoare proprie.; 5. O familie de grafice are expansiune mărginită dacă toți minorii săi $r-de$ jos au un raport de margini la vârfuri mărginite de o funcție a lui $r$ și expansiune polinomială dacă funcția lui $r$ este un polinom.

F

față: Într-un grafic plan sau încorporarea unui grafic , o componentă conectată a subsetului planului sau suprafeței încorporării care este disjunsă de grafic. Pentru o încastrare în plan, toate fețele, cu excepția unei singure, vor fi delimitate; singura față excepțională care se extinde până la infinit se numește fața exterioară.
factor: Un factor al unui grafic este un subgraf care acoperă: un subgraf care include toate vârfurile grafului. Termenul este utilizat în principal în contextul subgrafelor regulate: un factor $k$ este un factor care este $k-$ regulat. În special, un factor $1$ este același lucru cu o potrivire perfectă. Un grafic factor-critic este un grafic pentru care ștergerea oricărui vârf produce un grafic cu un factor $1$ .
factorizarea: O factorizare a graficului este o partiție a marginilor graficului în factori; o $k-$ factorizare este o partiție în $k-$ factori. De exemplu, o $1-$ factorizare este o culoare de margine cu proprietatea suplimentară că fiecare vârf este incident la o margine de fiecare culoare.
familie: Un sinonim pentru clasă .
finit: Un grafic este finit dacă are un număr finit de vârfuri și un număr finit de muchii. Multe surse presupun că toate graficele sunt finite fără a spune în mod explicit acest lucru. Un grafic este local finit dacă fiecare vârf are un număr finit de muchii incidente. Un grafic infinit este un grafic care nu este finit: are infinit de multe vârfuri, infinit de multe muchii sau ambele.
prima comanda: Logica de prima ordine a graficelor este o formă de logică în care variabilele reprezintă vârfurile unui grafic și există un predicat binar pentru a testa dacă două vârfuri sunt adiacente. De deosebit de logica de ordinul doi, în care variabilele pot reprezenta și seturi de vârfuri sau margini.
-flap: Pentru un set de noduri $X$ , un $X$ -flap este o componentă conectată a subgraful format prin eliminarea $X$ . Terminologia clapetei este frecvent utilizată în contextul paradisurilor , funcții care mapează seturi mici de vârfuri la clapele lor. A se vedea, de asemenea, puntea unui ciclu, care este fie o clapetă a vârfurilor ciclului, fie o coardă a ciclului.
interzis: O caracterizare interzisă a graficului este o caracterizare a unei familii de grafice ca fiind graficele care nu au anumite alte grafice ca subgrafe, subgrafe induse sau minori. Dacă $H$ este unul dintre graficele care nu apare ca subgraf, subgraf indus sau minor, atunci se spune că $H$ este interzis.
pădure: O pădure este un grafic nedirecționat fără cicluri (o uniune disjunctă a copacilor rădăcinați) sau un grafic direcționat format ca o uniune disjunctă a copacilor înrădăcinați.
Frucht: 1. Robert Frucht; 2. Graficul Frucht , unul dintre cele două mici grafice cubice, fără simetrii netiviale.; 3. Teorema lui Frucht că fiecare grup finit este grupul de simetrii ale unui grafic finit.
deplin: Sinonim pentru indus .
grafic funcțional: Un grafic funcțional este un grafic direcționat în care fiecare vârf are unul în afara gradului. În mod echivalent, un grafic funcțional este un pseudoforest direct maxim.

G

G: O variabilă utilizată adesea pentru a indica un grafic.
gen: Genul unui grafic este genul minim al unei suprafețe pe care poate fi încorporat; vezi încorporarea .
geodezică: Ca substantiv, o geodezică este un sinonim pentru o cale mai scurtă . Când este folosit ca adjectiv, înseamnă legat de cele mai scurte căi sau distanțe mai scurte ale căii.
gigant: În teoria graficelor aleatorii , o componentă gigantică este o componentă conectată care conține o fracție constantă a vârfurilor grafului. În modelele standard de grafice aleatorii, există de obicei cel mult o componentă gigantică.
circumferinţă: Girth unui grafic este lungimea ciclului său cel mai scurt.
grafic: Obiectul fundamental de studiu în teoria graficelor, un sistem de vârfuri conectate în perechi prin margini. Adesea subdivizate în grafice direcționate sau grafice nedirecționate în funcție de faptul dacă marginile au sau nu o orientare. Graficele mixte includ ambele tipuri de margini.
lacom: Produs de un algoritm lacom . De exemplu, o colorare lacomă a unui grafic este o colorare produsă luând în considerare vârfurile într-o anumită secvență și atribuind fiecărui vârf prima culoare disponibilă.
Grötzsch: 1. Herbert Grötzsch; 2. Graficul Grötzsch , cel mai mic grafic fără triunghi care necesită patru culori în orice colorare adecvată.; 3. Teorema lui Grötzsch conform căreia graficele plane fără triunghi pot fi întotdeauna colorate cu cel mult trei culori.
Numărul Grundy: 1. Numărul Grundy al unui grafic este numărul maxim de culori produse de o colorare lacomă , cu o ordonare de vârf greșit aleasă.

H

H: O variabilă adesea utilizat pentru a desemna un grafic, în special atunci când un alt grafic a fost deja notat cu $G$ .
H- colorare: O $H$ -coloring unui grafic $G$ (unde $H$ este de asemenea un grafic) este un homomorfism de la $H$ la $G$ .
H- gratuit: Un grafic este $H-$ liber dacă nu are un subgraf indus izomorf la $H$ , adică dacă $H$ este un subgraf indus interzis. Cele $H$ graficele -FREE sunt familia tuturor graficelor (sau, de multe ori, toate graficele finite) care sunt $H$ -free. De exemplu, graficele fără triunghi sunt graficele care nu au un grafic triunghi ca subgraf. Proprietatea de a fi lipsit de $H$ este întotdeauna ereditară. Un grafic este $H$ -minor-free în cazul în care nu are un izomorfă minor la $H$ .
Hadwiger: 1. Hugo Hadwiger; 2. Numărul Hadwiger al unui grafic este ordinea celui mai mare minor complet al graficului. Se mai numește și numărul clicei de contracție sau gradul de omomorfism.; 3. Conjectura Hadwiger este presupunerea că numărul Hadwiger nu este niciodată mai mic decât numărul cromatic.
Hamiltonian: O cale hamiltoniană sau un ciclu hamiltonian este o cale simplă de întindere sau un ciclu simplu de întindere: acoperă toate vârfurile din grafic exact o dată. Un grafic este hamiltonian dacă conține un ciclu hamiltonian și trasabil dacă conține o cale hamiltoniană.
refugiu: Un $k$ - haven este o funcție care mapează fiecare set $X$ de mai puțin de $k$ vârfuri la unul dintre clapele sale, îndeplinind adesea condiții de consistență suplimentare. Ordinea unui refugiu este numărul $k$ . Paradisurile pot fi folosite pentru a caracteriza lățimea arborelui graficelor finite și capetele și numerele Hadwiger ale graficelor infinite.
înălţime: 1. Înălțimea unui nod dintr-un copac înrădăcinat este numărul de margini dintr-o cale maximă, care se îndepărtează de rădăcină (adică nodurile sale au o adâncime strict crescătoare), care începe de la acel nod și se termină la o frunză.; 2. Înălțimea unui copac înrădăcinat este înălțimea rădăcinii sale. Adică, înălțimea unui copac este numărul de margini pe o cale mai lungă posibilă, care se îndepărtează de rădăcină, care începe de la rădăcină și se termină la o frunză.; 3. Înălțimea unui grafic aciclic direcționat este lungimea maximă a unei căi direcționate în acest grafic.
ereditar: O proprietate ereditară a graficelor este o proprietate care este închis sub subgrafurilor induse: în cazul în care $G$ are o proprietate ereditară, atunci așa trebuie să subgraf indus în fiecare $G$ . Comparați monoton (închis sub toate subgrafele) sau minor-închis (închis sub minori).
hexagon: Un ciclu simplu format din exact șase muchii și șase vârfuri.
gaură: O gaură este un ciclu indus cu lungimea de patru sau mai mult. O gaură ciudată este o gaură de lungime ciudată. Un anti-gaură este un subgraf indus de ordinul patru al cărui complement este un ciclu; echivalent, este o gaură în graficul complementului. Această terminologie este utilizată în principal în contextul graficelor perfecte, care se caracterizează prin teorema graficului perfect perfect ca fiind graficele fără găuri impare sau anti-găuri impare. Graficele fără găuri sunt aceleași cu graficele corale .
echivalența homomorfă: Două grafice sunt echivalente omomorf dacă există două homomorfisme, unul de la fiecare grafic la celălalt grafic.
homomorfism: 1. Un homomorfism grafic este o mapare de la setul de vârfuri ale unui grafic la setul de vârfuri ale unui alt grafic care mapează vârfurile adiacente la vârfurile adiacente. Acest tip de mapare între grafice este cel care este cel mai frecvent utilizat în abordările teoretice de categorii ale teoriei graficelor. O colorare corectă a graficului poate fi descrisă în mod echivalent ca un omomorfism cu un grafic complet.; 2. Gradul de omomorfism al unui grafic este un sinonim pentru numărul lui Hadwiger , ordinea celui mai mare clice minor.
hiperge: O margine într-un hipergraf , având orice număr de puncte finale, spre deosebire de cerința ca marginile graficelor să aibă exact două puncte finale.
hipercub: Un grafic hipercub este un grafic format din vârfurile și marginile unui hipercub geometric .
hipergraf: Un hipergraf este o generalizare a unui grafic în care fiecare margine (numită hiperge în acest context) poate avea mai mult de două puncte finale.
hipo-: Acest prefix, în combinație cu o proprietate de grafic, indică un grafic care nu are proprietatea, dar astfel încât fiecare subgraf format prin ștergerea unui singur vârf să aibă proprietatea. De exemplu, un grafic hipohamiltonian este unul care nu are un ciclu hamiltonian, dar pentru care fiecare ștergere cu un singur vârf produce un subgraf hamiltonian. Comparați critice , utilizate pentru grafice care au o proprietate, dar pentru care fiecare ștergere cu un singur vârf nu are.

Eu

în grad: Numărul de muchii primite într-un grafic direcționat; vezi gradul .
incidenţă: O incidență într-un grafic este o pereche vârf-margine astfel încât vârful să fie un punct final al marginii.
matrice de incidență: Matricea de incidență a unui grafic este o matrice ale cărei rânduri sunt indexate de noduri ale grafului și ale căror coloane sunt indexate de margini, cu una din celula pentru rândul $i$ și coloana $j$ când vertex $i$ și marginea $j$ sunt incidente, și zero altfel.
incident: Relația dintre o margine și unul dintre punctele sale finale.
incomparabilitate: Un grafic de incomparabilitate este complementul unui grafic de comparabilitate ; vezi comparabilitate .
independent: 1. Un set independent este un set de vârfuri care induce un subgraf fără margini. Poate fi numit și un set stabil sau un coclique. Numărul de independență $α (G)$ este mărimea setului maxim independent .; 2. În matroidul grafic al unui grafic, un subset de margini este independent dacă subgraful corespunzător este un copac sau o pădure. În matroidul circular , un subset de margini este independent dacă subgraful corespunzător este un pseudoforest .
indiferenţă: Un grafic de indiferență este un alt nume pentru un grafic de interval adecvat sau un grafic de interval de unitate; vezi corect .
induse: Un subgraf indus sau subgraf complet al unui grafic este un subgraf format dintr-un subset de vârfuri și din toate marginile care au ambele puncte finale în subset. Cazurile speciale includ căi induse și cicluri induse, subgrafe induse care sunt căi sau cicluri.
inductiv: Sinonim pentru degenerat .
infinit: Un grafic infinit este unul care nu este finit; vezi finit .
intern: Un vârf al unei căi sau al unui copac este intern dacă nu este o frunză; adică dacă gradul său este mai mare decât unul. Două căi sunt disjuncte la nivel intern (unii oameni o numesc independentă ) dacă nu au niciun vârf în comun, cu excepția primului și ultimului.
intersecție: 1. Intersecția a două grafice este cel mai mare subgraf comun al acestora, graficul format din vârfurile și muchiile care aparțin ambelor grafuri.; 2. Un grafic de intersecție este un grafic ale cărui vârfuri corespund seturilor sau obiectelor geometrice, cu o margine între două vârfuri exact atunci când cele două seturi sau obiecte corespunzătoare au o intersecție neocupată. Mai multe clase de grafice pot fi definite ca graficele de intersecție ale anumitor tipuri de obiecte, de exemplu , graficele acordurilor ( graficele de intersecție ale subarborilor unui copac), graficele de cerc (graficele de intersecție ale acordurilor unui cerc), graficele de interval (graficele de intersecție ale intervalelor) a unei linii), grafice de linie ( grafice de intersecție ale marginilor unui grafic) și grafice de clică (grafice de intersecție a clicurilor maxime ale unui grafic). Fiecare grafic este un grafic de intersecție pentru o anumită familie de mulțimi, iar această familie se numește o reprezentare de intersecție a graficului. Numărul de intersecție al unui grafic $G$ este numărul minim total de elemente în orice reprezentare intersecție $G$ .
interval: 1. Un grafic de interval este un grafic de intersecție al intervalelor unei linii .; 2. Intervalul $[u, v]$ dintr-un grafic este unirea tuturor celor mai scurte căi de la $u$ la $v$ .; 3. Grosimea intervalului este un sinonim pentru lățimea căii .
invariant: Un sinonim al proprietății .
săgeată inversată: O săgeată cu direcție opusă în comparație cu o altă săgeată. Săgeata $(y, x)$ este săgeata inversată a săgeții $(x, y)$ .
izolat: Un vârf izolat al unui grafic este un vârf al cărui grad este zero, adică un vârf fără margini incidente.
izomorfă: Două grafice sunt izomorfe dacă există un izomorfism între ele; vezi izomorfism .
izomorfism: Un izomorfism grafic este o incidență unu-la-unu care păstrează corespondența vârfurilor și marginilor unui grafic cu vârfurile și muchiile altui grafic. Se spune că două grafice legate în acest fel sunt izomorfe.
izoperimetric: Vezi extinderea .
istm: Sinonim pentru bridge , în sensul unei muchii a cărei eliminare deconectează graficul.

K

K: Pentru notația graficelor complete, graficelor bipartite complete și graficelor multipartite complete, consultați complet .
κ: $κ (G)$ (folosind litera greacă kappa) este ordinea clicei maxime din $G$ ; vezi clica .
nucleu: Un nucleu al unui grafic direcționat este un set de vârfuri care este atât stabil cât și absorbant .
nod: O secțiune inevitabilă a unui grafic direcționat . A se vedea nodul (matematica) și teoria nodurilor .

L

L: $L (G)$ este graficul liniar al lui $G$ ; vezi linia .
eticheta: 1. Informații asociate cu un vârf sau o margine a unui grafic. Un grafic etichetat este un grafic ale cărui vârfuri sau margini au etichete. Termenii etichetați la vârf sau etichetați la margine pot fi folosiți pentru a specifica ce obiecte ale unui grafic au etichete. Etichetarea graficelor se referă la mai multe probleme diferite de atribuire a etichetelor graficelor supuse anumitor constrângeri. Vezi și colorarea graficului , în care etichetele sunt interpretate ca culori.; 2. În contextul enumerării graficului , se spune că vârfurile unui grafic sunt etichetate dacă toate se disting între ele. De exemplu, acest lucru poate fi făcut adevărat prin fixarea unei corespondențe unu-la-unu între vârfuri și numere întregi de la 1 la ordinea graficului. Când vârfurile sunt etichetate, graficele care sunt izomorfe între ele (dar cu diferite ordonări ale vârfurilor) sunt numărate ca obiecte separate. În schimb, atunci când vârfurile sunt neetichetate, graficele care sunt izomorfe între ele nu sunt numărate separat.
frunze: 1. Un vârf frunzei sau vârf pandantiv (mai ales într-un copac) este un vârf al cărui grad este $1$ . O margine a frunzei sau marginea pandantivului este marginea care leagă un vârf al frunzei de vecinul său unic.; 2. O putere a frunzei unui copac este un grafic ale cărui vârfuri sunt frunzele arborelui și ale cărui margini leagă frunze a căror distanță în arbore este cel mult un prag dat.
lungime: Într-un grafic neponderat, lungimea unui ciclu, cale sau mers este numărul de margini pe care le folosește. Într-un grafic ponderat, poate fi în schimb suma ponderilor marginilor pe care le folosește. Lungimea este utilizată pentru a defini calea cea mai scurtă , circumferința (cea mai scurtă lungime a ciclului) și cea mai lungă cale între două vârfuri dintr-un grafic.
nivel: 1. Aceasta este adâncimea unui nod plus 1, deși unii îl definesc ca fiind sinonim al adâncimii . Nivelul unui nod într-un copac înrădăcinat este numărul de noduri din calea de la rădăcină la nod. De exemplu, rădăcina are nivelul 1 și oricare dintre nodurile sale adiacente are nivelul 2.; 2. Un set de noduri având același nivel sau adâncime.
linia: Un sinonim pentru o margine neorientată. Linie grafic $L (G)$ a unui grafic $G$ este un grafic cu un vârf pentru fiecare muchie a $G$ și o muchie pentru fiecare pereche de muchii care împart un obiectiv în $G$ .
legătură: Un sinonim pentru degenerare .
listă: 1. O listă de adiacență este o reprezentare computerizată a graficelor pentru utilizare în algoritmi grafic.; 2. Colorarea listei este o variație a colorării graficului în care fiecare vârf are o listă a culorilor disponibile.
local: O proprietate locală a unui grafic este o proprietate care este determinată doar de vecinătățile vârfurilor din grafic. De exemplu, un grafic este local finit dacă toate vecinătățile sale sunt finite.
buclă: O buclă sau auto-buclă este o margine ale cărei puncte finale sunt aceleași vârf. Formează un ciclu de lungime $1$ . Acestea nu sunt permise în grafice simple.

M

mărire: Sinonim pentru expansiunea vertexului .
potrivire: O potrivire este un set de margini în care niciunul nu împarte vreun vârf. Un vârf este asortat sau saturat dacă este unul dintre punctele finale ale unei margini în potrivire. O potrivire perfectă sau potrivire completă este o potrivire care se potrivește cu fiecare vârf; poate fi, de asemenea, numit factor 1 și poate exista numai atunci când ordinea este uniformă. O potrivire aproape perfectă, într-un grafic cu ordine impar, este una care saturează toate, cu excepția unui singur vârf. O potrivire maximă este o potrivire care utilizează cât mai multe margini posibil; numărul de potrivire $α' (G)$ al unui grafic $G$ este numărul de muchii dintr-o potrivire maximă. O potrivire maximă este o potrivire la care nu pot fi adăugate margini suplimentare.
maximal: 1. Un subgraf al graficului dat $G$ este maxim pentru o anumită proprietate dacă are acea proprietate, dar niciun alt supergraf al acesteia care este, de asemenea, un subgraf al lui $G$ are, de asemenea, aceeași proprietate. Adică este un element maxim al subgrafelor cu proprietatea. De exemplu, o clică maximă este un subgraf complet care nu poate fi extins la un subgraf complet mai mare. Cuvântul „maxim” ar trebui să se distingă de „maxim”: un subgraf maxim este întotdeauna maxim, dar nu neapărat invers.; 2. Un grafic simplu cu o proprietate dată este maxim pentru acea proprietate dacă nu este posibil să îi adăugați mai multe muchii (păstrând vârful setat neschimbat) păstrând în același timp simplitatea graficului și proprietatea. Astfel, de exemplu, un grafic plan maxim este un grafic plan, astfel încât adăugarea mai multor margini la acesta ar crea un grafic non-plan.
maxim: Un subgraf al unui grafic dat $G$ este maxim pentru o anumită proprietate dacă este cel mai mare subgraf (după ordine sau mărime) dintre toate subgrafele cu acea proprietate. De exemplu, o clică maximă este oricare dintre cele mai mari clici dintr-un grafic dat.
median: 1. O mediană a unui triplu de vârfuri, un vârf care aparține celor mai scurte căi între toate perechile de vârfuri, în special în grafice mediane și grafice modulare .; 2. Un grafic median este un grafic în care fiecare trei vârfuri au o mediană unică.
Meyniel: 1. Henri Meyniel, teoretician grafic francez.; 2. Un grafic Meyniel este un grafic în care fiecare ciclu impar de lungime cinci sau mai mult are cel puțin două coarde.
minim: Un subgraf al unui grafic dat este minim pentru o anumită proprietate dacă are acea proprietate, dar niciun subgraf adecvat al acesteia nu are, de asemenea, aceeași proprietate. Adică este un element minim al subgrafelor cu proprietatea.
tăiere minimă: O tăietură al cărei set de tăieturi are greutatea totală minimă, posibil limitată la tăieturi care separă o pereche desemnată de vârfuri; sunt caracterizate prin teorema debitului minim de debit maxim .
minor: Un grafic $H$ este un minor al unui alt grafic $G$ dacă $H$ pot fi obținute prin ștergerea marginilor sau noduri din $G$ și muchiile contractante în $G$ . Este un minor superficial dacă poate fi format ca minor în așa fel încât subgrafele lui $G$ care au fost contractate pentru a forma vârfurile lui $H$ au toate un diametru mic. $H$ este un minor topologic al $G$ dacă $G$ are un subgraf care este o subdiviziune a $H$ . Un grafic este $H$ -fără minori dacă nu are $H$ ca minor. O familie de grafice este minor-închisă dacă este închisă sub minori; Robertson-Seymour teoremă caracterizează familiile închise minore ca având un set finit de interzise minorilor.
amestecat: Un grafic mixt este un grafic care poate include ambele margini direcționate și nedirecționate.
modular: 1. Grafic modular , un grafic în care fiecare triplu de vârfuri are cel puțin un vârf median care aparține celor mai scurte căi între toate perechile triplului.; 2. Descompunerea modulară , o descompunere a unui grafic în subgrafe în cadrul cărora toate vârfurile se conectează la restul graficului în același mod.; 3. Modularitatea unui cluster grafic, diferența numărului de margini cross-cluster față de valoarea sa așteptată.
monoton: O proprietate monotonă grafice este o proprietate care este închis sub subgrafurilor: în cazul în care $G$ are o proprietate ereditară, atunci așa trebuie fiecare subgraf al $G$ . Comparați ereditar (închis sub subgrafe induse) sau minor-închis (închis sub minori).
Graficul Moore: Un grafic Moore este un grafic regulat pentru care legătura Moore este îndeplinită exact. Limita Moore este o inegalitate care leagă gradul, diametrul și ordinea unui grafic, dovedită de Edward F. Moore . Fiecare grafic Moore este o cușcă.
multigraf: Un multigraf este un grafic care permite adiacențe multiple (și, adesea, auto-bucle); un grafic care nu trebuie să fie simplu.
adiacență multiplă: O adiacență multiplă sau muchie multiplă este un set de mai multe margini care au toate aceleași puncte finale (în aceeași direcție, în cazul graficelor direcționate). Un grafic cu margini multiple este adesea numit multigraf.
multiplicitate: Multiplicitatea unei muchii este numărul de muchii într-o adiacență multiplă. Multiplicitatea unui grafic este multiplicitatea maximă a oricăreia dintre muchiile sale.

N

N: 1. Pentru notația pentru cartierele deschise și închise, consultați cartierul .; 2. Se folosește adesea o minusculă $n$ (mai ales în informatică) pentru a indica numărul de vârfuri dintr-un grafic dat.
vecin
vecin: Un vârf care este adiacent unui vârf dat.
Cartier
Cartier: Cartier deschis (sau cartier) a unui nod $v$ este subgraful indus de toate nodurile care sunt adiacente $v$ . Cartierul închis este definit în același mod, dar include și $v în$ sine. Vecinătatea deschisă a lui $v$ în $G$ poate fi notată $N G (v)$ sau $N (v)$ , iar vecinătatea închisă poate fi notată $N G [v]$ sau $N [v]$ . Când deschiderea sau închiderea unui cartier nu este specificată, se presupune că este deschisă.
reţea: Un grafic în care atributele (de exemplu, numele) sunt asociate cu nodurile și / sau marginile.
nodul: Un sinonim pentru vârf .
non-edge: Un non-edge sau anti-edge este o pereche de vârfuri care nu sunt adiacente; marginile grafului complementului.
grafic nul: Vezi graficul gol .

O

ciudat: 1. Un ciclu impar este un ciclu a cărui lungime este impară. Girth ciudat al unui grafic non-bipartit este lungimea ciclului său cel mai scurt ciudat. O gaură impară este un caz special al unui ciclu impar: unul care este indus și are patru sau mai multe vârfuri.; 2. Un vârf impar este un vârf al cărui grad este impar. Prin lema strângerii de mână, fiecare grafic finit nedirecționat are un număr par de vârfuri impare.; 3. O ureche impară este o cale simplă sau un ciclu simplu cu un număr impar de margini, utilizat în descompunerea urechii impare a graficelor critice pentru factor; vezi urechea .; 4. O coardă impară este o margine care leagă două vârfuri care se află la o distanță impar într-un ciclu par. Acordurile impare sunt folosite pentru a defini graficele puternic acorde .; 5. Un grafic impar este un caz special al unui grafic Kneser , având un vârf pentru fiecare $(n - 1)$ subset de element al unui set de elemente $(2 n - 1)$ și o margine care leagă două subseturi atunci când seturile lor corespunzătoare sunt disjunct.
deschis: 1. Vezi cartierul .; 2. Vezi mersul pe jos .
Ordin: 1. Ordinea unui grafic $G$ este numărul vârfurilor sale, $| V (G) |$ . Variabila $n$ este adesea utilizată pentru această cantitate. A se vedea, de asemenea , dimensiunea , numărul de margini.; 2. Un tip de logică a graficelor ; vezi ordinea întâi și ordinea a doua .; 3. O ordine sau ordonarea unui grafic este o dispunere a vârfurilor sale într-o succesiune, în special în contextul ordonării topologice (o ordine a unui grafic aciclic direcționat în care fiecare margine merge de la un vârf mai vechi la un vârf ulterior în ordine ) și ordonarea degenerării (o ordine în care fiecare vârf are un grad minim în subgraful indus al acestuia și în toate vârfurile ulterioare).; 4. Pentru ordinea unui refugiu sau a unei mărăcini, vezi Paradis și mărăcini .
orientare
orientat: 1. O orientare a unui grafic nedirectat este o atribuire a direcțiilor către marginile sale, transformându-l într-un grafic direcționat. Un grafic orientat este unul căruia i s-a atribuit o orientare. Deci, de exemplu, un polytree este un arbore orientat; diferă de un copac direcționat (o arborescență) prin faptul că nu există nicio cerință de consistență în direcțiile marginilor sale. Alte tipuri speciale de orientare includ turnee , orientări ale graficelor complete; orientări puternice , orientări puternic conectate; orientări aciclice , orientări aciclice; Orientări eulerian , orientări care sunt eulerian; și orientări tranzitive , orientări închise tranzitiv.; 2. Grafic orientat, folosit de unii autori ca sinonim pentru un grafic direcționat .
în afara gradului: Vezi gradul .
exterior: Vezi fața .
exteriorplanar: Un grafic exterior este un grafic care poate fi încorporat în plan (fără încrucișări) astfel încât toate vârfurile să fie pe fața exterioară a graficului.

P

cale: O cale poate fi o plimbare sau o plimbare fără vârfuri repetate și, în consecință, margini (numită și o cale simplă), în funcție de sursă. Cazurile speciale importante includ căi induse și căi scurte .
descompunerea căii: O descompunere a căii unui grafic $G$ este o descompunere a copacilor al cărei copac subiacent este o cale. Lățimea sa este definită în același mod ca și pentru descompunerea copacilor, ca una mai mică decât dimensiunea celui mai mare sac. Lățimea minimă a oricărei descompunere calea $G$ este pathwidth lui $G$ .
lățimea căii: Pathwidth unui grafic $G$ este lățimea minimă a unei descompuneri calea $G$ . Acesta poate fi de asemenea definite în ceea ce privește numărul clica de finalizare interval de $G$ . Este întotdeauna între lățime de bandă și treewidth de $G$ . Este, de asemenea, cunoscut sub numele de grosimea intervalului, numărul de separare a vârfurilor sau numărul de căutare a nodului.
pandantiv: Vezi frunza .
perfect: 1. Un grafic perfect este un grafic în care, în fiecare subgraf indus, numărul cromatic este egal cu numărul clici. Perfecta teorema graficului si Graficul perfect , puternic teoremă sunt două teoreme despre grafice perfecte, fostul dovedind că complementele lor sunt perfecte , iar acesta din urmă să demonstreze că acestea sunt exact graficele fără găuri ciudate sau anti-găuri.; 2. Un grafic perfect ordonabil este un grafic ale cărui vârfuri pot fi ordonate în așa fel încât un algoritm de colorat lacom cu această ordonare să coloreze optim fiecare subgraf indus. Graficele perfect ordonabile sunt o subclasă a graficelor perfecte.; 3. O potrivire perfectă este o potrivire care saturează fiecare vârf; vezi potrivire .; 4. O factorizare 1 perfectă este o partiție a marginilor unui grafic în potriviri perfecte, astfel încât fiecare două potriviri formează un ciclu hamiltonian.
periferic: 1. Un ciclu periferic sau un ciclu care nu separă este un ciclu cu cel mult un pod.; 2. Un vârf periferic este un vârf a cărui excentricitate este maximă. Într-un copac, aceasta trebuie să fie o frunză.
Petersen: 1. Julius Petersen (1839–1910), teoretician grafic danez.; 2. Graficul Petersen , un grafic cu 10 vârfuri cu 15 margini utilizat frecvent ca contraexemplu.; 3. Teorema lui Petersen conform căreia fiecare grafic cub fără punte are o potrivire perfectă.
planar: Un grafic plan este un grafic care are o încorporare în planul euclidian. Un grafic plan este un grafic plan pentru care a fost deja fixată o anumită încorporare. Un grafic $k-$ planar este unul care poate fi trasat în plan cu cel mult $k$ traversări pe margine.
polytree: Un polytree este un arbore orientat; în mod echivalent, un grafic aciclic direcționat al cărui grafic subiacent nedirectat este un copac.
putere: 1. O putere grafică $G k$ a unui grafic $G$ este un alt grafic pe același set de vârfuri; două vârfuri sunt adiacente în $G k$ , atunci când acestea sunt la distanță de cel mult $k$ din $G$ . O putere a frunzei este un concept strâns legat, derivat dintr-o putere a unui copac prin luarea subgrafului indus de frunzele arborelui.; 2. Analiza graficului de putere este o metodă de analiză a rețelelor complexe prin identificarea unor clici, biciclete și stele în rețea.; 3. Legile puterii în distribuțiile de grade ale rețelelor fără scară sunt un fenomen în care numărul vârfurilor unui anumit grad este proporțional cu o putere a gradului.
predecesor: Un vârf care vine înaintea unui vârf dat într-o cale direcționată .
corect: 1. Un subgraf propriu-zis este un subgraf care elimină cel puțin un vârf sau margine față de întregul grafic; pentru graficele finite, subgrafele adecvate nu sunt niciodată izomorfe pentru întregul grafic, dar pentru graficele infinite pot fi.; 2. O colorare adecvată este o atribuire a culorilor vârfurilor unui grafic (o colorare) care atribuie culori diferite punctelor finale ale fiecărei muchii; vezi culoarea .; 3. Un grafic de interval adecvat sau un grafic de arc circular adecvat este un grafic de intersecție al unei colecții de intervale sau arcuri circulare (respectiv) astfel încât niciun interval sau arc să nu conțină un alt interval sau arc. Graficele de interval adecvate se mai numesc și grafice de intervale unitare (deoarece pot fi întotdeauna reprezentate prin intervale de unitate) sau grafice de indiferență.
proprietate: O proprietate a graficului este ceva care poate fi adevărat pentru unele grafice și fals pentru altele și care depinde doar de structura graficului și nu de informații accidentale, cum ar fi etichetele. Proprietățile graficului pot fi descrise în mod echivalent în termeni de clase de grafice (graficele care au o proprietate dată). Mai general, o proprietate a graficului poate fi, de asemenea, o funcție a graficelor, care este din nou independentă de informațiile accidentale, cum ar fi dimensiunea, ordinea sau gradul de succes al unui grafic; această definiție mai generală a unei proprietăți este numită și un invariant al graficului.
pseudoforest: Un pseudoforest este un grafic nedirecționat în care fiecare componentă conectată are cel mult un ciclu sau un grafic direcționat în care fiecare vârf are cel mult o margine de ieșire.
pseudograf: Un pseudograf este un grafic sau multigraf care permite auto-buclele.

Î

grafic cvasi-liniar: Un grafic cvasi-linie sau un grafic local bipartit este un grafic în care vecinătatea deschisă a fiecărui vârf poate fi partiționată în două clici. Aceste grafice sunt întotdeauna fără gheare și includ ca caz special graficele liniare . Acestea sunt utilizate în teoria structurii graficelor fără gheare.
frison: Un tremur este un multigraf direcționat, așa cum este utilizat în teoria categoriilor . Marginile unei tolva se numesc săgeți.

R

rază: Raza unui grafic este excentricitatea minimă a oricărui vârf.
Ramanujan: Un grafic Ramanujan este un grafic a cărui expansiune spectrală este cât mai mare posibil. Adică, este un grafic $d-$ regulat, astfel încât a doua cea mai mare valoare proprie a matricei sale de adiacență este cel mult . ${\ displaystyle 2 {\ sqrt {d-1}}}$
raza: O rază, într-un grafic infinit, este o cale simplă infinită cu exact un punct final. La capetele unui grafic sunt clase de echivalență ale razelor.
accesibilitate: Capacitatea de a ajunge de la un vârf la altul într-un grafic .
accesibil: Are o accesibilitate afirmativă . Se spune că un vârf $y$ este accesibil de la un vârf $x$ dacă există o cale de la $x$ la $y$ .
recunoscut: În contextul conjecturii de reconstrucție , o proprietate a graficului poate fi recunoscută dacă adevărul său poate fi determinat din pachetul graficului. Se știe că multe proprietăți ale graficului pot fi recunoscute. Dacă conjectura reconstrucției este adevărată, toate proprietățile grafului sunt recunoscute.
reconstrucţie: Conjectura reconstrucție afirmă că fiecare grafic neorientat $G$ este unic determinată său de punte , un multiset de grafice formate prin îndepărtarea unui nod din $G$ în toate modurile posibile. În acest context, reconstrucția este formarea unui grafic din punte.
dreptunghi: Un ciclu simplu format din exact patru muchii și patru vârfuri.
regulat: Un grafic este $d-$ regulat atunci când toate vârfurile sale au gradul $d$ . Un grafic regulat este un grafic care este $d-$ regulat pentru unii $d$ .
turneu regulat: Un turneu obișnuit este un turneu în care gradul este egal cu gradul în afara gradului pentru toate vârfurile.
verso: Vezi transpunere .
rădăcină: 1. Un vârf desemnat într-un grafic, în special în arborii direcționați și graficele înrădăcinate .; 2. Operația inversă la o putere a graficului : a $k-$ a rădăcină a unui grafic $G$ este un alt grafic pe același set de vârfuri astfel încât două vârfuri sunt adiacente în $G$ dacă și numai dacă au distanță cel mult $k$ în rădăcină.

S

a doua comanda: Logica de ordinul doi al graficelor este o formă de logică în care variabilele pot reprezenta vârfuri, muchii, seturi de vârfuri și (uneori) seturi de margini. Această logică include predicate pentru testarea dacă un vârf și o margine sunt incidente, precum și dacă un vârf sau o margine aparține unui set. De deosebit de logica de ordinul întâi, în care variabilele pot reprezenta doar vârfuri.
saturat: Vezi potrivirea .
numărul de căutare: Numărul de căutare nod este un sinonim pentru lățimea căii .
auto-buclă: Sinonim pentru buclă .
vârf de separare: Vezi punctul de articulare .
numărul de separare: Numărul de separare a vertexului este un sinonim pentru lățimea căii .
simplu: 1. Un grafic simplu este un grafic fără bucle și fără adiacențe multiple. Adică, fiecare margine conectează două puncte finale distincte și nu există două margini care să aibă aceleași puncte finale. O margine simplă este o margine care nu face parte dintr-o adiacență multiplă. În multe cazuri, se presupune că graficele sunt simple, cu excepția cazului în care se specifică altfel.; 2. O cale simplă sau un ciclu simplu este o cale sau ciclu care nu are vârfuri repetate și, prin urmare, nu are margini repetate.
chiuvetă: O chiuvetă, într-un grafic direcționat, este un vârf fără margini de ieșire (gradul egal este 0).
mărimea: Dimensiunea unui grafic $G$ este numărul muchiilor sale, $| E (G) |$ . Variabila $m$ este adesea utilizată pentru această cantitate. Vezi și ordinea , numărul de vârfuri.
rețea din lumea mică: O rețea din lumea mică este un grafic în care majoritatea nodurilor nu sunt vecine una cu cealaltă, dar la majoritatea nodurilor se poate ajunge din orice alt nod printr-un număr mic de hamei sau pași. În mod specific, o rețea din lumea mică este definită ca un grafic în care distanța tipică L dintre două noduri alese aleator (numărul de pași necesari) crește proporțional cu logaritmul numărului de noduri N din rețea
snark: Un snark este un grafic cub simplu, conectat, fără punte, cu indice cromatic egal cu 4.
sursă: O sursă, într-un grafic direcționat, este un vârf fără margini de intrare (în grade este egal cu 0).
spaţiu: În teoria graficului algebric , mai multe spații vectoriale peste câmpul binar pot fi asociate cu un grafic. Fiecare are seturi de muchii sau vârfuri pentru vectorii săi și diferență simetrică de seturi ca operație de sumă vectorială. Spațiul de margine este spațiul tuturor seturilor de margini, iar spațiul de vârf este spațiul tuturor seturilor de vârfuri. Spațiul tăiat este un sub spațiu al spațiului de margine care are ca elemente seturile de tăiere ale graficului. Spațiul ciclului are ca elemente subgrafele euleriene.
cheie: O cheie este un grafic (de obicei rar) ale cărui distanțe de cale mai scurte se apropie de cele dintr-un grafic dens sau alt spațiu metric. Variațiile includ chei geometrice , grafice ale căror vârfuri sunt puncte într-un spațiu geometric; chei de copaci, copaci care acoperă un grafic ale căror distanțe se apropie de distanțele grafului și chei de grafic, subgrafe rare ale unui grafic dens ale cărui distanțe aproximează distanțele grafului original. O cheie lacomă este o cheie grafică construită de un algoritm lacom, în general unul care ia în considerare toate muchiile de la cea mai scurtă la cea mai lungă și păstrează cele necesare pentru a păstra aproximarea distanței.
care se întinde: Un subgraf se întinde atunci când include toate vârfurile graficului dat. Cazurile importante includ acoperirea copacilor , acoperirea subgrafelor care sunt copaci și potriviri perfecte , acoperirea subgrafelor care sunt potriviri. Un subgraf care se întinde poate fi numit, de asemenea, un factor , mai ales (dar nu numai) atunci când este regulat.
rar: Un grafic rar este unul care are câteva muchii în raport cu numărul său de vârfuri. În unele definiții, aceeași proprietate ar trebui să fie adevărată și pentru toate subgrafele grafului dat.
spectral
spectru: Spectrul unui grafic este colecția de valori proprii ale matricei sale de adiacență. Teoria graficului spectral este ramura teoriei graficelor care folosește spectrele pentru a analiza graficele. Vezi și expansiunea spectrală .
Despică: 1. Un grafic împărțit este un grafic ale cărui vârfuri pot fi partiționate într-o clică și un set independent. O clasă înrudită de grafice, graficele duble împărțite, sunt folosite în dovada teoremei grafului perfect puternic.; 2. O împărțire a unui grafic arbitrar este o partiție a vârfurilor sale în două subseturi neocupate, astfel încât marginile care se întind pe această tăietură formează un subgraf bipartit complet. Diviziunile unui grafic pot fi reprezentate printr-o structură de copac numită descompunerea sa divizată . O împărțire se numește o împărțire puternică atunci când nu este traversată de nicio altă împărțire. O despărțire se numește netivială atunci când ambele părți ale sale au mai mult de un vârf. Un grafic se numește prim atunci când nu are despărțiri netiviale.
pătrat: 1. Pătratul unui grafic $G$ este puterea graficului $G 2$ ; în cealaltă direcție, $G$ este rădăcina pătrată a lui $G 2$ . Jumătate de pătrat unui grafic bipartit este subgraful de pătrat sale induse de o parte a bipartiția.; 2. Un grafic pătrat este un grafic plan care poate fi desenat astfel încât toate fețele delimitate să fie de 4 cicluri și toate vârfurile de grad ≤ 3 să aparțină feței exterioare.; 3. Un grafic cu grilă pătrată este un grafic cu rețea definit din puncte din plan cu coordonate întregi conectate prin margini cu lungimea unității.
grajd: Un set stabil este un sinonim pentru un set independent .
stea: O stea este un copac cu un vârf intern; în mod echivalent, este un grafic bipartit complet $K 1, n$ pentru unele $n \geq 2$ . Cazul special al unei stele cu trei frunze se numește gheară.
putere: Puterea unui grafic este raportul minim al numărului de muchii eliminate din graful componentelor create, peste toate recoltările posibile; este analog cu duritatea, bazat pe îndepărtarea vertexului.
puternic: 1. Pentru conectivitate puternică și componente puternic conectate ale graficelor direcționate, consultați conexiunea și componentele . O orientare puternică este o orientare puternic conectată; vezi orientarea .; 2. Pentru teorema graficului perfect puternic , vezi perfect .; 3. Un grafic puternic regulat este un grafic regulat în care fiecare două vârfuri adiacente au același număr de vecini partajați și fiecare doi vârfuri non-adiacente au același număr de vecini partajați.; 4. Un grafic puternic acord este un grafic acord în care fiecare ciclu par de lungime șase sau mai mult are un acord impar.; 5. Un grafic puternic perfect este un grafic în care fiecare subgraf indus are un set independent care îndeplinește toate clice maxime. De Graficele Meyniel sunt , de asemenea , numite „foarte puternic grafice perfecte“ pentru că în ele, fiecare nod aparține unui astfel de set de independent.
subpădure: Un subgraf al unei păduri .
subgraf: Un subgraf al unui graf $G$ este un alt grafic format dintr - un subset al nodurilor și marginile $G$ . Subsetul de vârf trebuie să includă toate punctele finale ale subsetului de margine, dar poate include și vârfuri suplimentare. Un subgraf care se întinde este unul care include toate vârfurile grafului; un subgraf indus este unul care include toate muchiile ale căror puncte finale aparțin subsetului de vârf.
subarbore: Un subarbore este un subgraf conectat al unui copac. Uneori, pentru copacii înrădăcinați, subarborii sunt definiți ca fiind un tip special de subgraf conectat, format din toate vârfurile și marginile accesibile de la un vârf ales.
succesor: Un vârf care vine după un vârf dat într-o cale direcționată .
superconcentrator: Un superconcentrator este un grafic cu două subseturi desemnate și de dimensiuni egale de vârfuri $I$ și $O$ , astfel încât pentru fiecare două subseturi de dimensiuni egale $S$ de $I$ și $T$ $O$ există o familie de căi disjuncte care leagă fiecare vârf din $S$ la un vârf din $T$ . Unele surse necesită, în plus, ca un superconcentrator să fie un grafic aciclic direcționat, cu $I$ ca surse și $O$ ca chiuvete.
supergraf: Un grafic format prin adăugarea de vârfuri, muchii sau ambele la un grafic dat. Dacă $H$ este un subgraf de $G$ , atunci $G$ este o Supergraph de $H$ .

T

theta: 1. Un grafic teta este uniunea a trei căi disjuncte interne (simple) care au aceleași două vârfuri distincte.; 2. Graficul teta al unei colecții de puncte din planul euclidian este construit prin construirea unui sistem de conuri care înconjoară fiecare punct și adăugarea unei margini pe con, până la punctul a cărui proiecție pe o rază centrală a conului este cea mai mică.; 3. Numărul Lovász sau funcția Lovász theta a unui grafic este un grafic invariant legat de numărul clică și numărul cromatic care poate fi calculat în timp polinomial prin programare semidefinită.
topologic: 1. Un grafic topologic este o reprezentare a vârfurilor și marginilor unui grafic prin puncte și curbe în plan (nu neapărat evitând încrucișările).; 2. Teoria topologică a graficului este studiul încorporării graficelor.; 3. Sortarea topologică este problema algoritmică a aranjării unui grafic aciclic direcționat într-o ordine topologică, o secvență de vârf astfel încât fiecare margine să treacă de la un vârf mai devreme la un vârf ulterior din secvență.
total deconectat: Sinonim pentru fără margini .
tur: O pistă închisă, o plimbare care începe și se termină pe același vârf și nu are margini repetate. Tururile Euler sunt tururi care utilizează toate marginile graficului; vezi Eulerian .
turneu: Un turneu este o orientare a unui grafic complet; adică este un grafic direcționat astfel încât fiecare două vârfuri sunt conectate de exact o margine direcționată (mergând doar într-una din cele două direcții dintre cele două vârfuri).
trasabil: Un grafic trasabil este un grafic care conține o cale Hamiltoniană.
poteca: O plimbare fără margini repetate.
tranzitiv: Având în vedere proprietatea tranzitivă . Închiderea tranzitive unui grafic direcționat dat este un grafic pe același set vertex care are o margine de la un nod la altul ori de câte ori graficul original , are o cale care leagă aceleași două vârfuri. O reducere tranzitivă a unui grafic este un grafic minim având aceeași închidere tranzitivă; graficele aciclc direcționate au o reducere tranzitivă unică. O orientare tranzitivă este o orientare a unui grafic care este propria închidere tranzitivă; există doar pentru graficele de comparabilitate .
transpune: Graficul transpusa unui grafic direcționat dat este un grafic pe aceleași vârfuri, cu fiecare muchie inversat în direcția. Poate fi numit și invers sau invers al graficului.
copac: 1. Un copac este un grafic nedirect care este atât conectat, cât și aciclic, sau un grafic direcționat în care există o plimbare unică de la un vârf (rădăcina arborelui) la toate vârfurile rămase.; 2. Un $k-$ arbore este un grafic format prin lipirea $(k + 1)$ -clici împreună pe $k-$ clici împărtășite . Un copac în sensul obișnuit este $1$ arbore conform acestei definiții.
descompunerea copacilor: O descompunere a unui arbore a unui grafic $G$ este un arbore ale cărui noduri sunt etichetate cu seturi de vârfuri ale lui $G$ ; aceste seturi se numesc pungi. Pentru fiecare vârf $v$ , sacii care conțin $v$ trebuie să inducă un subarbore al copacului, iar pentru fiecare margine $uv$ trebuie să existe un sac care să conțină atât $u$ cât și $v$ . Lățimea descompunerii unui copac este cu una mai mică decât numărul maxim de vârfuri din oricare dintre pungi; treewidth de $G$ este lățimea minimă a oricărui descompunere arbore de $G$ .
lățimea copacului: Treewidth unui grafic $G$ este lățimea minimă a unui arbore de descompunere $G$ . Acesta poate fi , de asemenea , definite în ceea ce privește numărul clica de o finalizare a curburii a $G$ , ordinul unui refugiu de $G$ , sau ordinul unui rugi de $G$ .
triunghi: Un ciclu de lungime trei într-un grafic. Un grafic fără triunghi este un grafic nedirecționat care nu are niciun subgraf de triunghi.
Turan: 1. Pál Turán; 2. Un grafic Turan este un grafic multipartit complet echilibrat.; 3. Teorema Turan afirmă că graficele Turan au numărul maxim de muchii dintre toate graficele fără clici dintr-o ordine dată.; 4. Problema fabricii de cărămizi a lui Turan cere numărul minim de traversări într-un desen al unui grafic bipartit complet.

U

nedirecționat: Un grafic nedirectat este un grafic în care cele două puncte finale ale fiecărei muchii nu sunt distinse între ele. Vezi și regizat și mixt . Într-un grafic mixt , o margine nedirecționată este din nou una în care punctele finale nu sunt distinse între ele.
uniformă: Un hipergraf este $k$ -uniform atunci când toate marginile sale au $k$ puncte finale și uniform atunci când este $k$ -uniform pentru unii $k$ . De exemplu, graficele obișnuite sunt aceleași cu $2-$ hipergrafe uniforme.
universal: 1. Un grafic universal este un grafic care conține ca subgrafe toate graficele dintr-o anumită familie de grafice sau toate graficele de o anumită dimensiune sau ordine într-o anumită familie de grafice.; 2. Un vârf universal (numit și vârf sau vârf dominant) este un vârf care este adiacent oricărui alt vârf din grafic. De exemplu, graficele rotilor și graficele de prag conectate au întotdeauna un vârf universal.; 3. În logica graficelor , un vârf care este cuantificat universal într-o formulă poate fi numit vârf universal pentru formula respectivă.
grafic neponderat: Un grafic ale cărui vârfuri și muchii s nu au primit greutatea s ; opusul unui grafic ponderat .

V

V: Vezi setul de vârfuri .
valenţă: Sinonim pentru grad .
vârf: Un vârf (vârfuri la plural) este (împreună cu muchiile) una dintre cele două unități de bază din care sunt construite graficele. Vârfurile graficelor sunt adesea considerate a fi obiecte atomice, fără structură internă.
vârf tăiat
set de separare: Un set de noduri a căror îndepărtare deconecteaza Graficul . O tăietură cu un singur vârf se numește punct de articulație sau vârf tăiat .
set de vârfuri: Ansamblul vârfurilor unui grafic dat $G$ , uneori notat cu $V (G)$ .
vârfuri: Vezi vârf .
Vizing: 1. Vadim G. Vizing; 2. Teorema lui Vizing conform căreia indicele cromatic este cel mult cu mai mult decât gradul maxim.; 3. Conjectura lui Vizing asupra numărului de dominație a produselor carteziene ale graficelor.
volum: Suma gradelor unui set de vârfuri.

W

$W$: Litera $W$ este utilizată în notație pentru graficele roților și graficele morilor de vânt . Notarea nu este standardizată.
Wagner: 1. Klaus Wagner; 2. Graficul Wagner , o scară Möbius cu opt vârfuri.; 3. Teorema lui Wagner care caracterizează graficele plane de către minorii lor interziși.; 4. Teorema lui Wagner care caracterizează graficele $K 5$ -minore-free.
mers pe jos: O plimbare este o secvență finită sau infinită de muchii care unește o succesiune de vârfuri . Plimbările se mai numesc uneori lanțuri . O plimbare este deschisă dacă primul și ultimul său vârf sunt distincte și închisă dacă sunt repetate.
slab conectat: Un grafic direcționat se numește slab conectat dacă înlocuirea tuturor marginilor sale direcționate cu margini nedirecționate produce un grafic conectat (nedirectat).
greutate: O valoare numerică, atribuită ca etichetă unui vârf sau muchie a unui grafic. Greutatea unui subgraf este suma greutăților vârfurilor sau marginilor din acel subgraf.
grafic ponderat: Un grafic cărora vârfurile sau muchia s -a atribuit greutatea s ; mai precis, un grafic ponderat pe vârf are greutăți pe vârfuri, iar un grafic ponderat pe margini are greutăți pe margini.
bine colorate: Un grafic bine colorat este un grafic a cărui colorare lacomă folosește același număr de culori.
bine acoperit: Un grafic bine acoperit este un grafic ale cărui seturi maxime independente au aceeași dimensiune.
roată: Un grafic al roților este un grafic format prin adăugarea unui vârf universal la un ciclu simplu.
lăţime: 1. Un sinonim pentru degenerare .; 2. Pentru alți invarianți de grafic cunoscuți ca lățime, consultați lățimea de bandă , lățimea de ramură , lățimea de clică , lățimea de cale și lățimea de copac .; 3. Lățimea unei descompuneri a copacilor sau a descompunerii căii este cu una mai mică decât dimensiunea maximă a unuia dintre sacii săi și poate fi utilizată pentru a defini lățimea copacului și lățimea căii.; 4. Lățimea unui grafic aciclic direcționat este cardinalitatea maximă a unui anticaten.
moara de vant: Un grafic al morii de vânt este uniunea unei colecții de clici, toate de aceeași ordine ca una cu cealaltă, cu un vârf comun care aparține tuturor clicurilor și tuturor celorlalte vârfuri și margini distincte.

Languages

In other projects

Glosar de teoria graficelor - Glossary of graph theory

Simboluri

A

B

C

D

E

F

G

H

Eu

K

L

M

N

O

P

Î

R

S

T

U

V

W

Vezi si

Referințe