pilnutinis grafas
grãfas (gr. graphō – rašau), aibių dvejetas (X, Y); čia X – taškų, vadinamų viršūnėmis, aibė, Y – tas viršūnes jungiančių atkarpų, vadinamų grafo briaunomis, aibė; grafų teorijos sąvoka. Pvz., miestų aibė (grafo viršūnės) ir juos jungiantys keliai (grafo briaunos) sudaro grafą. Dvi grafo viršūnės, sujungtos bent viena briauna, vadinamos gretimomis. Jei nurodoma viršūnių jungimo kryptis, briauna vadinama orientuota, jei nenurodoma – neorientuota. Grafas, turintis visas orientuotas briaunas, vadinamas orientuotuoju, visas neorientuotas – neorientuotuoju. Grafo viršūnės ν laipsniu vadinamas iš tos viršūnės išeinančių briaunų skaičius (žymimas degν). Viršūnė, kurios laipsnis lygus nuliui, vadinama izoliuotąja. Reguliariojo grafo visų viršūnių laipsniai vienodi, t. y. kiekviena viršūnė susieta su kitomis vienodu briaunų skaičiumi. Grafo keliu (maršrutu) vadinama seka, sudaryta iš gretimų viršūnių ir jas jungiančių briaunų. Kelias vadinamas ciklu, jei jis prasideda ir baigiasi ta pačia viršūne. Ciklas, kuris eina per kiekvieną viršūnę tik po vieną kartą, vadinamas Hamiltono ciklu.
Grafas vadinamas jungiu, jei bet kurias dvi jo viršūnes galima sujungti keliu. Kelias, kurį sudaro visos jungiojo grafo briaunos po vieną kartą, vadinamas Eulerio keliu. Jei šis kelias prasideda ir baigiasi toje pat grafo viršūnėje, kelias vadinamas Eulerio ciklu. Grafas turi Eulerio ciklą tada, kai visų jo viršūnių laipsniai lyginiai. Briauna, prasidedanti ir pasibaigianti ta pačia viršūne, vadinama kilpa. Pilnutinis grafas neturi kilpų; kiekviena jo viršūnių pora susieta tik viena briauna. Grafo briaunoms priskiriami tam tikri skaičiai, vadinami svoriais. Jie gali reikšti atstumą, laiką, išlaidas ir panašiai. Trumpiausias tokio grafo ciklas vadinamas optimaliu. Plokščiasis grafas yra toks, kurį galima vaizduoti plokštumoje taip, kad jo briaunos kirstųsi tik jo viršūnėse. Grafas, kurio kiekvieną viršūnę galima sujungti su bet kuria kita jo viršūne, vadinamas susijusiuoju. Toks grafas be ciklų vadinamas medžiu. Gramatikos orientuotasis grafas naudojamas programavimo kalbos gramatikos taisyklėms ir simboliams vaizdžiai pateikti. Grafai vaizduojami schemomis. Jais reiškiamos įvairių sistemų struktūros.
neorientuotasis grafas su 3 viršūnėmis, 3 briaunomis ir 4 kilpomis