Graph Theory Glossary

Graafiteooria sõnastik – Graph Theory Glossary

| # | a | b | c-cn | co | cp-cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz |
| n | o | p | q | r | s-so | sp-sz | t | u | v | w | xyz |

ear Path between old vertices through new vertices. [DW96]	kõrv Tee vanade tippude vahel läbi uute tippude.
ear decomposition Construction of G from a cycle by addition of ears. [DW96]	kõrva-dekompositsioon Graafi G konstrueerimine tsüklist kõrvade lisamise teel.
earliest finish time = EFT A length of the critical path of the network. [ISEM00]	varaseim lõpetusaeg Võrgu kriitilise tee pikkus.
Earth-Moon coloring problem What is the minimum number of colors necessary to color all Earth-Moon maps? [DA00]	Maa-Kuu kaartide värvimise ülesanne Milline on värvide miinimumarv, mida vajatakse kõigi Maa-Kuu kaartide värvimiseks?
easy problem A problem for which a polynomial-bounded algorithm has been founded. [BC79]	lihtne ülesanne Ülesanne, mille jaoks on olemas polünomiaalselt tõkestatud algoritm.
eccentricity = graph eccentricity Let G be a graph and v be a vertex of G. The eccentricity of the vertex v is the maximum distance from v to any vertex. That is, e(v) = max{d(v, w): w ĪV(G)} . [SL99] The eccentricity of a vertex is the length of the longest minimal path from that vertex to some vertex in the graph. [ISEM00]	ekstsentrilisus = graafi ekstsentrilisus Olgu G graaf ja v graafi G tipp. Tipu v ekstsentrilisus on maksimumkaugus tipust v suvalise tipuni, st e(v) = max{d(v, w): w ĪV(G)} . Tipu ekstsentrilisus on pikima miinimumtee pikkus antud tipust graafi mingi teise tipuni.
e-cordial labeling A labeling of a graph with e edges is called e-cordial if it is possible to label the edges with numbers from the set N = {0, 1} and when the induced vertex labels f(v) computed by f(v) = S "u f(u, v) (mod 2 ) , where v ĪV and {u, v} ĪE so that the conditions 1 ³ \| v_f (0) - v_f (1) \| and 1 ³ \| e_f (0) - e_f(1) \| are satisfied, where v_f(j) and e_f(j) , j = 0, 1 are, respectively, denote the number of vertices and edges labeled with 0's and 1's. The graph G is called e-cordial if it admits an e-cordial labeling. [IC00]	e-südamlik märgendus e servaga graafi märgendust nimetatakse e-südamlikuks, kui ta servad saab märgendada arvudega hulgast N = {0, 1} ning kui tekitatud tipumärgendid f(v) arvutatakse valemiga f(v) = S "uf(u, v) (mod 2 ) , kus v ĪV ja {u, v} Ī E , nii et on rahuldatud tingimused 1 ³ \| v_f (0) - v_f (1) \| ja 1 ³ \| e_f (0) - e_f(1) \| , kus v_f(j) ja e_f(j) , j = 0, 1 , tähistavad vastavalt tippude ja servade arvu, mis märgendatakse 0-de ning 1-dega. Graafi G nimetatakse e-südamlikuks, kui talle on võimalik rakendada e-südamlikku märgendust.
e-cordial graph The graph G is called e-cordial if it admits an e-cordial labeling. [IC00]	e-südamlik graaf e servaga graafi G nimetatakse e-südamlikuks, kui talle on võimalik rakendada e-südamlikku märgendust.
edge = link = line An edge in a graph is an unordered pair of nodes. In a directed graph, the edges are ordered pairs. [ODC00] A connection between two vertices of a graph. [PEB00] In a graph, a pair of vertices . In a hypergraph, a subset of the vertex set. [DW96] A connection between two vertices of a graph containing no other vertices. FIGURE	serv Graafi serv on tippude järjestamata paar. Orienteeritud graafis on servad (ehk kaared) tippude järjestatud paarid. Ühendus graafi kahe tipu vahel. Graafi tippude paar. Hüpergraafis tippude hulga alamhulk. Graafi kahte tippu ühendav joon, mis teisi tippe ei sisalda. [OO76] JOONIS
edge arboricity = arboricity	servapuisus = puisus
edge block A connected graph, not edgeless, that has no edge cutpoints. [TZ98] FIGURE	servaplokk Sidus graaf (vähemalt ühe servaga), milles pole ühtki servaliigendit. JOONIS
edge choosability Minimum k such that G is k-edge-choosable. [DW96]	servavalitavus Vähim k , mille puhul graaf G on k-servavalitav.
edge chromatic number = chromatic index	kromaatiline indeks
edge color class The set of all edges of a graph G receiving the same color in an edge coloring of G . [CL96]	servavärviklass Graafi G kõigi servade hulk, millele antakse graafi G servavärvingus sama värv.
edge coloring An edge coloring of a graph refers to the choice and arrangement of colors for the edges. Formally, an edge coloring of a graph is a one-to-one function from the set of the graphs's edges into the set of all colors. [ISEM00] An assignment of labels to the edges. [DW96] FIGURE	servavärving Viitab värvide valikule ja järjestamisele graafi servade jaoks. Formaalselt on graafi servavärving üksühene funktsioon servade hulgast värvide hulka. Märgendite kinnistamine servadele. JOONIS
edge component A maximal connected subgraph that contains an edge. A loose edge is an edge component but an isolated vertex is not. [TZ98] FIGURE	servkomponent Sidus maksimaalne alamgraaf, mis sisaldab vähemalt ühe serva. Lahtine serv on servkomponent, isoleeritud tipp aga mitte. JOONIS
edge connectivity = line connectivity The minimum number of edges whose deletion from a graph disconnects it. The edge connectivity of a disconnected graph is 0, while that of a connected graph with a bridge is 1. [EW00] The largest value of k for which G is k-edge-connected. [BW97]	servasidusus Servade miinimumarv, mille kustutamine graafist muudab graafi mittesidusaks. Sidusetu graafi servasidusus on 0, silda sisaldava graafi servasidusus aga 1. Arvu k suurim väärtus, mille puhul graaf G on k-servasidus.
edge contraction An edge-contraction on a graph G is the process of removing an edge e and identifying its incident vertices v and w in such a way that the resulting vertex is incident to those edges (other than e) which were originally incident to v or w . That is, after the contraction, the resulting graph H has one less vertex because v = w, and at least one less edge since edge e has been removed, and if there is any other vertex of G, say x, that is connected to both v and w, then those two edges are merged in H into one edge connecting x to v = w .[HC00]	serva ahendus Graafi G serva ahenduse käigus eemaldatakse serv e ja asendatakse tema otstipud v ning w uue tipuga, millega on intsidentsed kõik servad, mis olid esialgselt intsidentsed tippudega v ja w . Pärast ahendust tekkival graafil H on üks tipp vähem, kuna v = w , ja vähemalt üks serv vähem, kuna serv e eemaldati. Kui graafis G leidub mõni teine tipp (näiteksx), mis on ühendatud nii tipuga v kui ka w , siis need kaks serva mestitakse graafis H üheks servaks, mis ühendab tipu x uue tipuga v = w .
edge cover = hitting set Let G = (V, E) be an undirected graph. A subset A Ķ V is called an edge cover if for every edge xy ĪE , either xĪA or y ĪA or both. [MG80] Let S be a collection of subsets of a finite set X . The smallest subset Y of X that meets every member of S is called the edge cover, or hitting set. However, some authors call any such set a edge cover, and then refer to the minimum edge cover. [EW00] A set of edges incident to all vertices. [DW96] FIGURE	servakate Olgu G = (V, E) orienteerimata graaf. Alamhulka A Ķ V nimetatakse servakatteks, kui iga serva xy Ī E puhul kas xĪA või yĪA või mõlemad. Olgu S lõpliku hulga X alamhulkade kogum. Servakatteks nimetatakse hulga X vähimat alamhulka Y , millel on mittetühi ühisosa hulga S iga liikmega. Mõningad autorid kutsuvad servakatteks ka suvalise elementide arvuga vastavat hulka ning kasutavad vajaduse korral nimetust "minimaalne servakate". Servade hulk, mis on intsidentne kõigi tippudega. JOONIS
edge cover problem Given a graph G = (V, E) and positive integer K , is there an E' Ķ E with \|E'\|£K such that for each v Ī V there is some eĪE' for which vĪe ?[GJ79]	servakatte ülesanne Antud on graaf G = (V, E) ja positiivne täisarv K . Kas leidub alamhulk E' Ķ E , \|E'\|£K , nii et iga v Ī V jaoks on olemas eĪE' , mille puhul v Īe ?
edge covering The partitioning of a graph into sets of chains or circuits that collectively include all the edges in a graph. [CGM79] FIGURE	servadega katmine Graafi tükeldamine ahelate või tsüklite hulkadeks, mis ühiselt hõlmavad graafi kõiki servi. JOONIS
edge covering number The minimum cardinality of a edge cover in G . [CL96]	servakattearv Graafi G servakatte minimaalne võimsus.
edge crossing = crossing	servade lõikumine = lõikumine
edge cut = cut	lõige
edge cut vertex = edge cutpoint	servaliigend
edge cutpoint = edge cut vertex A vertex that is a cutpoint or that is incident to more than one edge of which one (at least) is a loop or half edge. [TZ98] FIGURE	servaliigend Tipp, mis on liigend, või mis on intsidentne enam kui ühe servaga, millest (vähemalt) üks on silmus või poolserv. JOONIS
edge disjoint union = EDU A collection of subsets of edges such that no two of these subsets have edges in common. [WM72] FIGURE	ühisservadeta ühend = EDU Servade alamhulkade kogum, kus ei leidu ühtki ühiseid servi omavate alamhulkade paari. JOONIS
edge embedding on a grid problem Given a graph G = (V, E) and positive integers M and N , is there a one-to-one function f : V ® {1, 2, … , M} ´ {1, 2, … , N} such that if {u, v} Ī E ,f(u) = (x₁ , y₁) and f(v) = (x₂ , y₂) , then either x₁ = x₂ or y₁ = y₂ ? [GJ79]	servade kujutamise ülesanne ruudustikul Antud on graaf G = (V, E) ja positiivsed täisarvud M ning N . Kas leidub üksühene funktsioon f : V ® {1, 2, … , M} ´ {1, 2, … , N} , nii et kui {u, v} Ī E ,f(u) = (x₁ , y₁) ja f(v) = (x₂ , y₂) , siis kas x₁ = x₂ või y₁ = y₂ ?
edge end An end of an edge may be considered to be an object in itself. Each end is incident with exactly one vertex. [TZ98]	serva ots Serva otsa võib käsitleda omaette objektina. Iga ots on intsidentne täpselt ühe tipuga.
edge-graceful graph Let f be an edge labeling of G where f : E(G) ® {1, 2, … ,e}, e = \| E(G) \| is one-to-one and f induces a label on the vertices f(v) = S _{uv Ī E(G)} f(uv) (mod n) , where n is the number of vertices of G . The labeling f is edge-graceful if all vertex labels are distinct modulo n in which case G is called an edge-graceful graph. Along many results on the graphs an important conjecture asserts that all trees with an odd number of vertices are edge-graceful. [IC00]	servapehme graaf Olgu antud graafi G üksühene servamärgendus f : E(G) ® {1, 2, … ,e}, e = \| E(G) \| , mis tekitab tippudele märgendi f(v) = S_uv Ī E(G) f(uv) (mod n) , kus n on graafi G tippude arv. Märgendus f on servapehme, kui kõigi tippude märgendid erinevad mooduli n järgi; sel juhul nimetatakse graafi G servapehmeks graafiks. Lisaks paljudele graafiteooria tulemustele väidab oluline hüpotees, et kõik paaritu tippude arvuga puud on servapehmed.
edge-graceful labeling Let f be an edge labeling of G where f : E(G) ® {1, 2, … ,e}, e = \| E(G) \| is one-to-one and f induces a label on the vertices f(v) = S _{uv Ī E(G)} f(uv) (mod n) , where n is the number of vertices of G . The labeling f is edge-graceful if all vertex labels are distinct modulo n in which case G is called an edge-graceful graph. [IC00]	servapehme märgendus Olgu antud graafi G üksühene servamärgendus f : E(G) ® {1, 2, … ,e}, e = \| E(G) \| , mis tekitab tippudele märgendi f(v) = S_uv Ī E(G) f(uv) (mod n) , kus n on graafi G tippude arv. Märgendus f on servapehme, kui kõigi tippude märgendid erinevad mooduli n järgi; sel juhul nimetatakse graafi G servapehmeks graafiks.
edge independence number The size of a largest independent edge set. [BW97]	servade sõltumatusaste Suurima sõltumatu servade hulga suurus.
edge induced subgraph An edge-induced subgraph consists of some of the edges of the original graph and the vertices that are at their endpoints. [ISEM00] For a set S of edges, we use G[S] to denote the edge induced subgraph of G whose edge set is S and whose vertex set is the subset of V(G) consisting of those vertices incident with any edge in S . [SL99] FIGURE	servade tekitatud alamgraaf Servade tekitatud alamgraaf koosneb esialgse graafi mõnedest servadest ja nende servade otspunktidest. Graafi G servade hulga S puhul olgu servade tekitatud alamgraaf G[S] , mille servade hulk on S ja tippude hulk on V(G) alamhulk, kuhu kuuluvad need tipud, mis on intsidentsed suvalise servaga hulgast S . JOONIS
edge number The number of edges in a graph. [EW00]	servade arv Graafi servade arv.
edge reconstructible A graph that can be determined (up to isomorphism) by knowing the multiset of subgraphs obtained by deleting single edges. [DW96]	servapõhiselt taastatav Graaf, mille saab (kuni isomorfismini) määrata alamgraafide multihulga järgi, mis on saadud üksikute servade kustutamise teel.
edge reconstruction conjecture The conjecture that every graph with at least four edges is edge-reconstructible.[DW96]	servapõhise taastamise hüpotees Hüpotees, mille järgi iga vähemalt nelja servaga graaf on servapõhiselt taastatav.
edge sequence A finite sequence of adjacent and not necessarily distinct edges that are traversed in going from v₀ to v_n .[CGM79]	servade jada Intsidentsete (mitte tingimata erinevate) servade lõplik jada, mida läbitakse siirdumisel tipust v₀ tippu v_n .
edge subdivision = elementary subdivision	serva jaotamine = elementaarjaotamine
edge thickness = thickness = graph thickness	servapaksus = paksus = graafi paksus
edge train A sequence of edges with the following properties: For any edge e other than the first and the last edges in the sequence, one endpoint of e is an endpoint of the preceding edge and the other endpoint of e is an endpoint of the succeeding edge. One endpoint of the first edge is and endpoint of the succeeding edge and the other endpoint of the first edge is the initial vertex. One endpoint of the last edge is and endpoint of the preceding edge and the other endpoint is the final vertex. Every edge appears exactly once. [WM72] FIGURE	servade ahel Servade jada järgmiste omadustega: Mistahes jadasse kuuluva serva e puhul (peale esimese ja viimase) langeb serva e üks otspunkt kokku eelmise serva otspunktiga ja serva e teine otspunkt järgmise serva otspunktiga. Esimese serva üks otspunkt on järgmise serva otspunktiks ja esimese serva teine otspunkt on algpunktiks. Viimase serva üks otspunkt on järgmise serva otspunktiks ja viimase serva teine otspunkt on lõpp-punktiks. Iga serv esineb täpselt ühe korra. JOONIS
edge transitive The group of isomorphisms from a graph G to itself is the automorphism group of G, Aut(G) . A graph G is edge-transitive if Aut(G) acts transitively on E(G) . [SL99] Existence of a permutation for each pair e, f ĪE(G) that maps e to f . [DW96]	servtransitiivne Graafi G automorfismirühm Aut(G) on graafi G isomorfismide rühm iseendasse. Graaf G on servtransitiivne, kui automorfismirühm Aut(G) toimib servade hulgal E(G) transitiivselt. Permutatsiooni olemasolu iga paari e, f ĪE(G) jaoks, mis kujutab serva e servaks f .
edge transitive automorhism group An automorphism group that contains automorphisms mapping each edge of G to every other edge. [BW97]	servtransitiivne automorfismirühm Automorfismirühm, kuhu kuuluvad automorfismid kujutavad graafi G iga serva mistahes teiseks servaks.
edge transitive graph A graph such that any two edges are equivalent under some element of its automorphism group. [EW00]	servtransitiivne graaf Graaf, mille suvalised kaks serva on tema automorfismirühma teatud elemendi järgi ekvivalentsed.
edge-width The edge-width of the embedding is the length of the shortest noncontractible cycle in the graph. The edge-width is no smaller than the face-width. [DA00]	servapõhine laius Graafi lühima mitteahendatava tsükli pikkus. Servapõhine laius ei ole väiksem kui tahupõhine laius.
Edmonds' map A nonreflexible regular map of genus 7 with eight vertices, 28 edges, and eight heptagonal faces. [EW00]	Edmondsi kaart Mitterefleksiivne regulaarne seitsmendat liiki kaart 8 tipu, 28 serva ja 8 kuusnurkse tahuga.
EDU = edge disjoint union	ühisservadeta ühend = EDU
efficient algorithm = fast algorithm	tõhus algoritm = kiire algoritm
effort Intensive power variable in a bond graph, one of the two complementary variables. See also flow. [KMR90] FIGURE	pingus Intensiivne võimsusmuutuja sidemegraafis, üks kahest komplementaarmuutujast. Vt ka voog. JOONIS
EFT = earliest finish time	varaseim lõpetusaeg
eigenvalue = graph eigenvalue The eigenvalues of a graph are defined as the eigenvalues of its adjacency matrix. The set of eigenvalues of a graph is called a graph spectrum. [EW00]	omaväärtus = graafi omaväärtus Graafi omaväärtused on määratletud graafi naabrusmaatriksi omaväärtustena. Graafi omaväärtuste hulka nimetatakse graafi spektriks.
eigenvector A vector x such that Ax = lx for some constant l . [DW96]	omavektor Vektor x , nii et Ax = lx teatud konstandi l puhul.
electrical network A structured object obtained by the interconnection of a collection of multiterminal devices. [HN97] An ordered pair (G, D) where G is a directed graph on the edge set E and D is a device characteristic. [HN97]	elektrivõrk Struktureeritud võrk, mis saadakse mitmeklemmiliste seadmete kogumi omavahelise ühendamise teel. Järjestatud paar (G, D) , kus G on orienteeritud graaf servade hulgal E ja D on seadmekarakteristik.
elegant graph Additive versions of graceful graphs are harmonious graphs and exact modular additive analogue versions of graceful graphs are called elegant graphs. Let Z_n be the additive group of integers modulo n and let G be a graph with n vertices. The graph G is said to be elegant if it is possible to label the vertices of G with distinct elements Z_n so that on labeling the edges with the sums of their endpoint labels, these edge labels are distinct and range over Z_n- {0} . An interesting result on elegant graphs is that the path with n vertices is elegant for all values of n except for n = 4 . [IC00]	elegantne graaf Pehme graafi aditiivne versioon on harmooniline graaf. Pehme graafi täpset modulaarset aditiivset analoogversiooni nimetatakse elegantseks graafiks. Olgu Z_n täisarvude aditiivne rühm mooduli n järgi ning olgu G n tipuga graaf. Graafi G nimetatakse elegantseks, kui tema tipud saab märgendada Z_n-i erinevate elementidega, nii et kinnistades servade märgenditeks nende otspunktide märgendite summad, osutuvad servade märgendid erinevateks ja kuuluvad väärtusvarusse Z_n- {0} . Huvitav tulemus elegantsete graafide kohta väidab, et n tipuga tee on elegantne kõigi n-ide puhul välja arvatud n = 4 .
element A vertex or an edge of a graph. [CL96]	element Graafi tipp või serv.
elementary chain A chain which does not traverse any node more than once. [BC79]	elementaarahel Ahel, mis ei läbi ühtki tippu mitu korda.
elementary path A path which does not traverse any node more than once. [BC79]	elementaartee Tee, mis ei läbi ühtki tippu mitu korda.
elementary separator The edges of a graph can be partitioned into blocks such that within each block every pair of distinct edges can be included in some circuit and edges belonging to different blocks cannot be included in the same circuit (each coloop would form a block by itself). Such a block is called an elementary separator of the graph. [HN97]	elementaareraldaja Graafi servad saab tükeldada plokkideks, nii et iga ploki piires mistahes kaks serva kuuluvad mõnda tsüklisse ning eri plokkidesse kuuluvaid servi ei saa panna samasse tsüklisse (iga kaassilmus moodustab omaette ploki). Sellist plokki nimetatakse graafi elementaareraldajaks.
elementary subdivision = edge subdivision Replacement of an edge by a path of two edges connecting the endpoints of the original edge. [DW96] If e = vw is an edge of G, then we obtain a new graph by replacing e by two new edges vz and zw , where z is a new vertex. [BW97]	elementaarjaotamine = serva jaotamine Serva asendamine kahest servast koosneva teega, mis ühendab esialgse serva otspunkte. Kui e = vw on graafi G serv, siis uue graafi saamiseks asendame serva e kahe uue servaga vz ja zw , kus z on uus tipp.
elimination degree sequence ordering Given a graph G = (V, E) and sequence < d₁, d₂ , … , d _\|V\|> of non-negative integers not exceeding \| V \| - 1 , is there a one-to-one function f : V ® { 1, 2, … , \| V \| } such that for 1 £i £ \| V \| , if f(v) = i then there are exactly d_i vertices u such that f(u) > i and {u, v} ĪE ? [GJ79]	elimineerimise astmejada järjestamine Antud on graaf G = (V, E) ning mittenegatiivsete täisarvude jada < d₁, d₂ , … , d _\|V\|> , mis ei ületa väärtust \| V \| - 1 . Kas on olemas üksühene funktsioon f : V ® { 1, 2, … , \| V \| } , nii et 1 £i £ \| V \| puhul kui f(v) = i , siis leidub täpselt d_i tippu u , mille jaoks f(u) > i ja {u, v} ĪE ?
embeddable graph = realizable graph	kujutatav graaf = realiseeritav graaf
embedding = graph embedding By embedding of a graph G in a surface S , each vertex of G becomes a point of S and each edge becomes a simple curve joining the corresponding points, and the curves do not meet except at their ends. [BW97] A mapping of a graph into a surface, such that (the images of) its edges do not intercept except for shared endpoints. [DW96]	graafi kujutamine Graafi G kujutamisel pinnal S muutub graafi G iga tipp pinna S punktiks ja iga serv vastavaid punkte ühendavaks lihtkõveraks, mis ei lõiku mujal kui otspunktides. Graafi esitamine pinnal, nii et servad (ehk nende kujutised) ei lõiku mujal kui vaid ühistes otspunktides.
empty graph An empty graph on n nodes consists of n isolated nodes with no edges. [EW00] FIGURE	tühigraaf Tühigraaf n tipul koosneb n isoleeritud tipust ja ei oma ühtki serva. JOONIS
empty set The set with no elements. [HN97]	tühihulk Hulk, mis ei sisalda ühtki elementi.
end block A block containing exactly one cut-vertex of G . [CL96]	otsplokk Plokk, mis sisaldab täpselt ühe graafi G lõiketipu.
end vertex = leaf	otstipp = leht
end vertex set The set of end vertices of a given crossing edge set. [HN97]	otstippude hulk Antud ristsidehulga otstippude hulk.
endpoint = root = leaf	juur = leht
endpoint of an edge Vertex to which the edge is incident. [TZ98]	serva otspunkt Tipp, millega serv on intsidentne.
enumeration problem The problem of determining (or counting) the set of all solutions to a given problem. [EW00]	loendusülesanne Antud probleemi kõigi lahendite määramise ehk loendamise ülesanne.
equal sets The sets which have the same members. [HN97]	võrdsed hulgad Samade liikmetega hulgad.
equipartite Having part-sizes differing by at most one. [DW96]	võrdtükeldatav Tükeldatav osadeks, mis erinevad mitte rohkem kui ühe võrra.
equitable coloring Having color classes differing in size by at most one. [DW96]	õiglane värving Värviklassid erinevad mitte rohkem kui ühe võrra.
equitable graph Equitable labeling of graphs is an natural generalization of cordial labelings. Label the vertices of a graph G with labels 0, 1, …, k , where k < e , (e is the number of the edges). The induced edge labels is given by the absolute difference of the vertex labels at its end-points. Then the graph G is called (k + 1)-equitable if the number of vertex (edge) labels is balanced. [IC00]	õiglane graaf Graafi õiglane märgendus on südamliku märgenduse loomulik üldistus. Graafi G tipud varustatakse märgenditega 0, 1, …, k , kus k < e , (e on servade arv). Tekitatud servamärgenditele omistatakse otspunktide tipumärgendite vahede absoluutväärtused. Graafi G nimetatakse (k + 1)-õiglaseks, kui tippude (servade) märgendite arv on tasakaalustatud.
equitable labeling Equitable labeling of graphs is an natural generalization of cordial labelings. Label the vertices of a graph G with labels 0, 1, …, k , where k < e , (e is the number of the edges). The induced edge labels is given by the absolute difference of the vertex labels at its end-points. [IC00]	õiglane märgendus Graafi õiglane märgendus on südamliku märgenduse loomulik üldistus. Graafi G tipud varustatakse märgenditega 0, 1, …, k , kus k < e , (e on servade arv). Tekitatud servamärgenditele omistatakse otspunktide tipumärgendite vahede absoluutväärtused.
equivalence As a graph, a union of disjoint cliques. [DW96]	ekvivalents Graafina ühisosata klikkide ühend.
equivalence relation Reflexive, symmetric, and transitive relation. [DW96]	ekvivalentsiseos Refleksiivne, sümmeetriline ja transitiivne seos.
equivalent vertices Vertices whose neighborhoods are equal. [MG80] FIGURE	ekvivalentsed tipud Tipud, mille naabrused on võrdsed. JOONIS
Erdös number Mathematicians assign Erdös the number 0. People who have coauthored a paper with him are given the number 1. As of May 1996, there were 462 such coauthors. Another 4,566 people have the number 2 because they wrote a paper not with Erdös himself but with someone who wrote a paper with Erdös. The Erdös number 3 goes to anyone who has collaborated with someone who has written a paper with someone who coauthored a paper with Erdös, and so on. Thus, any person not yet assigned an Erdös number who has written a joint mathematical paper with a person having an Erdös number n earns the Erdös number n + 1 . Anyone left out of this assignment process has the Erdös number infinity. [IP00] Distance from Erdös in the collaboration graph of mathematicians. [DW96]	Erdösi arv Matemaatikud on kinnistanud Erdösile arvu 0. Teadlastele, kes on koos temaga midagi publitseerinud, antakse arv 1. Seisuga mai 1996 oli selliseid kaasautoreid 462. Arvu 2 omavad 4 566 inimest, kuna nad on avaldanud midagi mitte koos Erdösi enda, vaid mõne tema kaasautoriga. Erdösi arv 3 läheb inimestele, kes on avaldanud artikli koos kellegagi, kes on teinud koostööd Erdösi kaasautoriga jne. Isik, kellel veel Erdösi arvu pole, kuid kes on kirjutanud ühise artikli koos Erdösi arvu n omava inimesega, saab endale seega Erdösi arvu n + 1 . Seni kinnistusprotsessist väljapoole jääva inimese Erdösi arvu väärtuseks loetakse lõpmatus. Kaugus Erdösist matemaatikute koostöögraafis.
Erdös-Stone theorem A generalization of Turįn's theorem to non-complete graphs. [EW00]	Erdös-Stone'i teoreem Turįni teoreemi üldistus mittetäielikele graafidele.
ERN = exchange rate network	valuutavõrk
Euclidean graph A weighted graph in which the weights are equal to the Euclidean lengths of the edges in a specified embedding. [EW00]	eukleidiline graaf Kaalutud graaf, kus kaalud võrduvad servade eukleidiliste pikkustega kindlal joonistusel.
Euclidean Steiner tree A tree of minimum Euclidean distance connecting a set of points, called terminals, in the plane. This tree may include points other than the terminals, which are called Steiner points. [PEB00]	eukleidiline Steineri puu Minimaalse eukleidilise kaugusega puu, mis ühendab punktide (terminalide) hulka tasapinnal. Puu võib sisaldada ka teisi punkte peale terminalide, mida kutsutakse Steineri punktideks.
Euclidean traveling salesman problem Find a path of minimum Euclidean distance between points in a plane which includes each point exactly once and returns to its starting point. [PEB00]	eukleidiline proovireisija ülesanne Leida minimaalse eukleidilise kaugusega tee tasapinna punktide vahel, mis sisaldab iga punkti täpselt ühe korra ning naaseb lähtepunkti.
Euler chain = Eulerian chain	Euleri ahel
Euler circuit = Euleriasn cycle	Euleri tsükkel
Euler cycle = Eulerian cycle	Euleri tsükkel
Euler digraph = Eulerian digraph	Euleri orienteeritud graaf
Euler graph = Eulerian graph	Euleri graaf
Euler path = Eulerian chain	Euleri tee
Euler polyhedron formula If V, E and F are the number of vertices, edges and faces of a polyhedron, then V – E + F = 2 .[CL96]	Euleri hulktahuka valem Kui V, E ja F on vastavalt hulktahuka tippude, servade ja tahkude arv, siis V – E + F = 2 .
Euler tour = Eulerian cycle	Euleri tsükkel
Eulerian chain = Eulerian path = Eulerian trail An Euler path is a path which traverses each edge of a graph exactly once. [DMP00] A chain which contains all edges of a graph. FIGURE	Euleri tee = Euleri ahel Tee, mis läbib graafi iga serva täpselt ühe korra. Ahel, mis sisaldab vaadeldava graafi kõik servad. [ÜK82] JOONIS
Eulerian circuit = Eulerian cycle	Euleri tsükkel
Eulerian cycle = Eulerian circuit = Eulerian tour A simple circuit of a graph in which every edge is traversed once and only once. [CGM79] An Eulerian path which is a circuit. [SW87] A closed trail containing every edge. [DW96] FIGURE	Euleri tsükkel Graafi lihttsükkel, kus iga serva läbitakse täpselt üks kord. Euleri tee, mis on tsükkel. Suletud tee, mis sisaldab kõiki servi. JOONIS
Eulerian digraph = Euler digraph A connected digraph D is Eulerian if it has a closed directed trail that includes every arc of D . [BW97] FIGURE	Euleri orienteeritud graaf Sidus orienteeritud graaf D , milles leidub suletud orienteeritud tee, kuhu kuuluvad graafi D kõik kaared. JOONIS
Eulerian graph = Euler graph A graph containing an Euler cycle. For (connected) undirected graphs, this is true iff every vertex has even degree. For directed graphs, this is true iff every vertex has equal indegree and outdegree. Planar bipartite graphs are dual to planar Eulerian graphs and vice versa. [ODC00] A connected graph G is Eulerian if it has a closed trail that includes every edge of G . [BW97] FIGURE	Euleri graaf Graaf, kus leidub Euleri tsükkel. Sidusate orienteerimata graafide puhul kehtib see siis ja ainult siis, kui graafi kõigi tippude aste on paarisarv. Orienteeritud graafide puhul kehtib see siis ja ainult siis, kui iga tipu suubeaste on võrdne väljumisastmega. Planaarsed bikromaatilised graafid on duaalsed planaarsete Euleri graafidega ja vastupidi. Sidus graaf G , kus leidub suletud tee, mis sisaldab graafi G kõiki servi. JOONIS
Eulerian path = Eulerian chain	Euleri tee = Euleri ahel
Eulerian tour = Eulerian cycle	Euleri tuur = Euleri tsükkel
Eulerian trail = Eulerian chain	Euleri tee = Euleri ahel
Euler's formula A formula relating the number of edges, and nodes of a graph to the number of regions into which it will divide the plane. Let G be a connected planar graph with n nodes and e edges which divides the plane into r regions. Then any one of n, e, and r may be determined from the other two by the relation n – e + r = 2 . [ODC00]	Euleri valem Valem, mis seob graafi servade ja tippude arvu tasapinnal moodustuvate piirkondade arvuga. Olgu G sidus planaarne graaf n tipu ja e servaga, mis jagab tasapinna r piirkonnaks. Nende vahel kehtib järgmine seos: n – e + r = 2 .
eve = endpoint = leaf = root	otspunkt = leht = juur
even cycle Cycle with an even number of edges (or vertices). [DW96] FIGURE	paaristsükkel Tsükkel, kuhu kuulub paarisarv servi (või tippe). JOONIS
even cycle matroid = lift matroid = even polygon matroid = factor matroid	paaristsüklimatroid = tõstematroid = paarishulknurgamatroid = faktormatroid
even cycle problem Given a digraph, does it contain an even-length cycle? [TZ98]	paaristsükli ülesanne Antud on orienteeritud graaf. Kas ta sisaldab paarisarvulise pikkusega tsüklit ?
even graph Graph with all vertex degrees even. [DW96] FIGURE	paarisgraaf Graaf, mille kõigi tippude astmed on paarisarvud. JOONIS
even pair Vertex pair x, y such that every chordless x, y-path has even length. [DW96]	paarispaar Tippude paar x, y , kusjuures iga kõõludeta x, y-tee pikkus on paarisarv.
even polygon matroid = lift matroid = even cycle matroid = factor matroid	paarishulknurgamatroid = tõstematroid = paaristsüklimatroid = faktormatroid
even triangle Triangle T such that every vertex has an even number of neighbors in T . [DW96]	paariskolmnurk Kolmnurk T , nii et igal tipul on T-s paarisarv naabreid.
even vertex A vertex with even degree. [CL96] FIGURE	paaristipp Paarisarvulise astmega tipp. JOONIS
evolution The model of generating random graphs by successively adding random edges . [DW96]	evolutsioon Mudel juhuslike graafide genereerimiseks juhuslike servade järjestikuse lisamise teel.
exchange rate network = ERN A pair (G, f) , in which G = (V, E) is a connected graph and f is a function defined on the set S of sides G , f ( w, v) ³ 0 , f ( w, v) = f ( v, w) ^-1 , and there is no possibility of profit by cyclic arbitrage, f ( v ₁ , v ₂) f ( v ₂ , v ₃) … f ( v _i , v ₁) = 1 . [BW97] FIGURE	valuutavõrk Paar (G, f) , kus G = (V, E) on sidus graaf ja f on graafi G orienteeritud servade hulgal S defineeritud funktsioon, f ( w, v) ³ 0 ,f ( w, v) = f (v, w) ^-1 , ning puudub võimalus kasu saamiseks tsükliliste arbitraažtehingute teel, f ( v ₁ , v ₂) f ( v ₂ , v ₃) … f ( v _i , v ₁) = 1 . JOONIS
exhaustive algorithm = brute-force algorithm Algorithms that are designed to examine systematically every possibility in search of a solution. Although exhaustive algorithms will theoretically produce a solution, often the amount of time or resources required to make the exhaustive search is prohibitive. [ISEM00]	ammendav algoritm = jõuline algoritm Algoritm, mis on loodud iga võimaluse süstemaatiliseks uurimiseks lahenduse otsimise käigus. Kuigi ammendav algoritm garanteerib teoreetiliselt lahendini jõudmise, ei võimalda vajalik aja ning ressursside maht tihtipeale siiski meetodit rakendada.
exhaustive circuit matrix A matrix B_e = [b_ij] , where b_ij = 1 if edge i is in circuit (or in edge disjoint union of circuits) j and b_ij = 0 otherwise. [WM72] FIGURE	täielik tsüklimaatriks Maatriks B_e = [b_ij] , kus b_ij = 1 , kui serv i kuulub tsüklisse (või ühisservadeta tsüklite ühendisse) j ning b_ij = 0 vastasel korral. JOONIS
exhaustive circuit matrix of oriented graph A matrix B_e = [b_ij] of order n_c´n_e where b_ij = 1 if edge j is in circuit (or in EDU of circuits) i and the orientation of edge agrees with that of circuit (or EDU of circuits), b_ij = -1 if edge j is in circuit (or in EDU of circuits) i and the orientation of edge disagrees with that of circuit (or EDU of circuits), b_ij = 0 otherwise. [WM72] FIGURE	orienteeritud graafi täielik tsüklimaatriks n_c ´ n_e-maatriks B_e= [b_ij] , kus b_ij = 1 , kui serv j kuulub tsüklisse (või ühisservadeta tsüklite ühendisse) i ning serva orientatsioon ühtib tsükli (või ühisservadeta tsüklite ühendi) orientatsiooniga; b_ij = -1 , kui serv j kuulub tsüklisse (või ühisservadeta tsüklite ühendisse) i ning serva orientatsioon ei ühti tsükli (või ühisservadeta tsüklite ühendi) orientatsiooniga; b_ij = 0 muul juhul. JOONIS
exhaustive cutset matrix A matrix Q_e = [q_ij] , where q_ij = 1 if edge i is in cutset (or in edge disjoint union of cutsets) j and q_ij = 0 otherwise. [WM72] FIGURE	täielik lõikemaatriks Maatriks Q_e = [q_ij] , kus q_ij = 1 , kui serv i kuulub lõikesse (või ühisservadeta lõigete ühendisse) j ning q_ij = 0 muul juhul. JOONIS
exhaustive cutset matrix of oriented graph A matrix Q_e = [q_ij] of order n_q´n_e where q_ij = 1 if edge j is in cutset (or in EDU of cutsets) i and the orientation of edge agrees with that of cutset (or EDU of cutsets), q_ij = -1 if edge j is in cutset (or in EDU of cutses) i and the orientation of edge disagrees with that of cutset (or EDU of cutsets), b_ij = 0 otherwise. [WM72] FIGURE	orienteeritud graafi täielik lõikemaatriks n_q ´ n_e-maatriks Q_e= [q_ij] , kus q_ij = 1 , kui serv j kuulub lõikesse (või ühisservadeta lõigete ühendisse) i ning serva orientatsioon ühtib lõike (või ühisservadeta lõigete ühendi) orientatsiooniga; q_ij = -1 , kui serv j kuulub lõikesse (või ühisservadeta lõigete ühendisse) i ning serva orientatsioon ei ühti lõike (või ühisservadeta lõigete ühendi) orientatsiooniga; b_ij = 0 muul juhul. JOONIS
exhaustive incidence matrix A matrix A_e = [a_ij] , where a_ij = 1 if edge i is incident at vertex j and a_ij = 0 otherwise. [WM72] FIGURE	täielik intsidentsmaatriks Maatriks A_e = [a_ij] , kus a_ij = 1 , kui serv i on intsidentne tipuga j , ning a_ij = 0 muul juhul. JOONIS
exhaustive incidence matrix of oriented graph A matrix A_e = [a_ij] of order n_v´n_e where a_ij = 1 if edge j is incident at vertex i and is oriented away from vertex i, a_ij = -1 if edge j is incident at vertex i and is oriented toward vertex i, a_ij = 0 otherwise. [WM72] FIGURE	orienteeritud graafi täielik intsidentsmaatriks n_v ´ n_e-maatriks A_e= [a_ij] , kus a_ij = 1 , kui serv j on intsidentne tipuga i ja suunatud tipust i eemale; a_ij = -1 , kui serv j on intsidentne tipuga i ja suunatud tipu i poole; a_ij = 0 muul juhul. JOONIS
existence problems A category of discrete mathematics which deals with whether a given problem has a solution or not. [DMP00]	olemasolu ülesanded Diskreetse matemaatika valdkond, mis uurib, kas antud ülesandel leidub lahend või ei.
expander A graph in which each set S of vertices that is not too big has many neighbors outside S . [BW97]	ekspander Graaf, kus igal mitte liiga suurel tippude hulgal S on palju naabreid väljaspool hulka S .
expansion In a 3-regular graph, subdividing two edges and joining the two new vertices by an edge.[DW96]	laiendus 3-regulaarses graafis kahe serva jaotamine ning tekkinud kahe uue tipu ühendamine servaga.
expansion lemma Adding a vertex of degree k to a k-connected graph preserves k-connectedness. [DW96]	laienduslemma Tipu astmega k lisamine k-sidusale graafile säilitab k-sidususe.
expansive property For a function s on the subsets of a set, the requirement that X Ķ s (X) for all X . [DW96]	laiendatavusomadus Hulga alamhulkadel määratud funktsiooni s jaoks nõue, et X Ķ s (X) kõigi X-de puhul.
expected complexity The average order of the running time over all problems of a given size. [BC79]	oodatav keerukus Keskmine tööaeg kõigi antud suurusega ülesannete lõikes.
exponential function Any function which is the sum of constants times other constants to the power of the argument: f(x) = S c_i b_ix^pi. In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by an exponential function of the problem size, n . [PEB00]	eksponentsiaalne funktsioon Suvaline summafunktsioon f(x) = S c_i b_ix^pi , kus liidetavad moodustatakse kolme teguri – ühe konstandi, teise konstandi ja argumendi astme – korrutamise teel. Keerukusteoorias on arvutuste mõõt m(n) (tavaliselt täitmisaeg või mäluruum) tõkestatud eksponentsiaalse funktsiooniga ülesande suurusest n .
exponential time algorithm Any algorithm whose time complexity cannot be bounded as a polynomial time function. [GJ79]	eksponetsiaalajaga algoritm Algoritm, mille ajakeerukust ei saa tõkestada kui polünomiaalajaga funktsiooni.
extended k-d-tree A spatial access method where successive levels are split along different dimensions into nonoverlapping cells. Objects are indexed in all cells they intersect. [PEB00]	laiendatud k-d-puu Ruumiline pöördusmeetod, kus järjestikused tasemed on tükeldatud eri dimensioonide lõikes mittekattuvatesse lahtritesse. Objektid indekseeritakse kõigis lahtrites, millega nad lõikuvad.
exterior region The unbounded region in a plane graph. [DW96]	välispiirkond Tõkestamata piirkond tasandgraafis.
exterior semidegree = outdegree	väljumisaste
extremal graph The largest graph of order n which does not contain a given graph G as a subgraph. [EW00]	ekstremaalgraaf Suurim n-järku graaf, mis ei sisalda antud graafi G alamgraafina.
extremal graph theory The study of how the intrinsic structure of graphs ensures certain types of properties (e.g., clique-formation and graph colorings) under appropriate conditions. [EW00]	ekstremaalne graafiteooria Valdkond, mis uurib graafide sisemise struktuuri rolli teatud tüüpi omaduste (nt klikkide ja värvingute) realiseerimisel asjakohastes tingimustes.
extreme vertex A vertex whose neighborhood is complete. [MG80]	piirtipp Tipp, mille naabrus on täielik.
extroverted edge Bidirected link or loop whose ends are both directed toward the endpoints. [TZ98]	ekstravertne serv Kahesuunaline serv või silmus, mille mõlemad otsad on suunatud otspunktide poole.

| # | a | b | c-cn | co | cp-cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz |

| n | o | p | q | r | s-so | sp-sz | t | u | v | w | xyz |

2002 Mati Littover ml@ioc.ee