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 |
    | marriage | matching | matroid | max | maximal | maximum | maximum flow | maximum matching | metric |
 
magic graph
An edge-magic graph is a labeled graph with n edges labeled with distinct elements {1, 2, … , n} so that the sum of the edge labels at each vertex is the same. A vertex-magic graph labeled vertices which give the same sum along every straight line segment. [EW00]
maagiline graaf
Servmaagiline graaf on märgendatud graaf, mille n serva märgendatakse eri elementidega {1, 2, … , n} , nii et tipuga intsidentsete servade märgendite summa on kõigis tippudes sama. Tippmaagilise graafi tipud on märgendatud nii, et tipumärgendite summa igal sirglõigul on sama.
JOONIS
magic labeling
It is conjectured that every tree with n edges whose nodes are all trivalent or monovalent can be given a "magic" labeling such that the integers 1, 2, ... , n can be assigned to the edges so that the sum of the three meeting at a node is constant. [EW00] 
maagiline märgendus
On olemas hüpotees, et iga n servaga puu, mille kõik tipud on kolme- või ühevalentsed, võimaldab "maagilist" märgendust, kus servadele kinnistatakse täisarvud 1, 2, ... , n nii, et tipuga intsidentse kolme serva märgendite summa on konstantne.
Malhotra-Kumar-Maheshwari blocking flow algorithm
Given a flow function and its corresponding residual graph (a maximum-flow problem), select a vertex with the least throughput and greedily push the maximum flow from it to the sink. This is repeated until all vertices are deleted. [PEB00]
Malhotra-Kumar-Maheshwari tõkkevoo algoritm
Antud voofunktsiooni ja sellele vastava jääkgraafi puhul (maksimumvoo ülesanne) valida vähima läbilaskevõimega tipp ja määrata maksimumvoog sellest tipust neeldu. Korrata seda, kuni kõik tipud on kustutatud.
M-alternating path
A path alternating between edges in M and not in M .[DW96]
M-alterneeruv tee
Tee, milles vahelduvad alamgraafi M kuuluvad ja mittekuluvad servad.
manpower planning problem 
This has many variations, but typically focuses on either short-term problems, like scheduling workers, or on longterm problems, like recruiting. There are workers of different categories, some relate to each other by level (e.g., copilot and pilot), others do not. For longterm manpower planning, inventory balance equations are typically used to represent changes in the number of employees in each category over time, including new hires and various forms of departures. For the short-term scheduling, a simple model is the shortest path through a network. Often, more complicated combinatorial optimization models are required. [HG99]
tööjõu plaanimise ülesanne 
Ülesandel on mitmeid variante, kuid tavaliselt hõlmab see kas lühiajalisi ülesandeid (nt töötajate ajakavade koostamine) või pikaajalisi ülesandeid (nt töötajate värbamine). Töötajad jagunevad klassidesse, kusjuures mõned klassid on seotud eri tasemete kaudu (nt piloot ja II piloot). Tööjõuressursside pikaajalise plaanimise puhul kasutatakse tavaliselt bilansivõrrandeid, mis kirjeldavad töötajate arvu igas klassis sõltuvalt ajast (arvestades uute töötajate värbamist ja erinevaid töölt lahkumisi). Lühiajaliste töökavade koostamisel on lihtsaim mudel lühima tee leidmine võrgus. Sageli ei saa läbi ilma keerukamate kombinatoorse optimeerimise mudeliteta.
map
A 3-connected plane graph. [BW97]
kaart
3-sidus tasandgraaf.
mapping
An arrangement f : X ® Y , denoted by f ( × ) , which associates with each element x ÎX the element y ÎY .[HN97]
kujutus
Vastavus f : X ® Y , mis seab iga elemendiga x Î X vastavusse elemendi y Î Y . Tähistus f ( × ) .
marked graph = vertex signed graph
märgitud graaf = märgitud tippudega graaf
Markov chain
A finite state machine with probabilities for each transition, that is, a probability that the next state is sj given that the current state is si . Equivalently, a weighted, directed graph in which the weights corresponding to the probability of that transition. In other words, the weights are nonnegative and the total weight of outgoing edges is positive. If the weights are normalized, the total weight, including self-loops, is 1. [PEB00]
Markovi ahel
Lõplik automaat üleminekutõenäosustega, st tõenäosusega, et antud oleku si korral on järgmine üleminek sj . Teiste sõnadega, kaalutud orienteeritud graaf, kus kaaludeks on ülemineku tõenäosused. Kaalud on mittenegatiivsed ja väljuvate servade kogukaal on positiivne. Kaalude normaliseerimisel on kogukaal koos silmustega 1.
Markov's inequality
For a nonnegative random variable, 

Prob(X ³ t) £E(X)/t . [DW96]
Markovi võrratus
Mittenegatiivse juhusliku suuruse puhul 

Prob(X ³ t) £E(X)/t .
marriage problem
Given a set of boys and a set of girls where each girl knows some of the boys, under what conditions can all girls get married, each to a boy she knows? [CL96]
abielu ülesanne 
Antud on noormeeste ja neidude hulk, kus iga neiu tunneb mõningaid noormehi. Millistel tingimustel saab iga neiu mehele tuttavale noormehele? 
marriage theorem = Frobenius theorem
Let G be a bipartite graph with bipartition V1 , V2 . Then G has a perfect matching (marriage) if and only if | V1 | = | V2 | and the V1-deficiency def(G) satisfies def(G) = 0 , where | X | denotes the cardinality of the set X .[HC00]		 abielu teoreem = Frobeniuse teoreem 
Olgu G bikromaatiline graaf kaksiktükeldusega 
V1 , V2 . Graafil G on täiuslik kate (abielu) siis ja ainult siis, kui | V1 | = | V2 | ja V1-defitsiit def(G) rahuldab seost def(G) = 0, kus | X | tähistab hulga X elementide arvu. 
martingale
Sequence of random variables such that 

E(Xi | X0, …, Xi-1) = Xi-1 . [DW96]
martingaal
Juhuslike muutujate jada X0, … , Xi , kusjuures 

E(Xi | X0, …, Xi-1) = Xi-1 .
matched edge
An edge which is in a matching. [PEB00]
katteserv
Serv, mis kuulub kattesse.
matched vertex
A vertex on an matched edge in a matching, or, one which has been matched. [PEB00]
kattetipp
Katteservaga intsidentne tipp või kattesse kuuluv tipp.
matching = independent edge set
A subgraph in which every vertex has a degree at most one. In other words, no two edges share a common vertex. [PEB00]
A set of pairwise independent edges. [CL96]
A matching in a graph is a set of edges such that every vertex of the graph is on at most one edge in the set. [WC00]
A 1-regular subgraph. [DW96]
kate = sõltumatu servade hulk
Alamgraaf, milles ühegi tipu aste ei ole suurem kui 1. Teiste sõnadega, ei leidu ühise tipuga servapaari.

Paariviisi sõltumatute servade hulk.
Graafi servade hulk, nii et graafi iga tipp on intsidentne vähemalt ühe sellesse hulka kuuluva servaga.

1-regulaarne alamgraaf.
JOONIS
matching number 
The number of edges in a maximum size matching in a graph G.[HC00]		 kattearv 
Servade arv graafi G maksimumsuurusega kattes.
matching problem 
Given a graph, a matching is a subgraph with the property that no two edges are incident to the same node. Subject to certain restrictions, the problem is to find a feasible matching that optimizes some objective, such as minimizing the total cost of the edges in the matching. A perfect matching is when each node is incident with exactly one edge. 

The assignment problem is a classical perfect matching, whereby the graph is bipartite (nodes are two sets: people and jobs), and the matching must have all nodes (every person must do a job, and every job must be done). Then, the matching corresponds precisely to an assignment since each job node is incident with exactly one person node in the matching. Further, the cost of each such matching is precisely the total cost of the corresponding assignment, so this min-cost matching problem is the same as the assignment problem. 
Another type of matching problem, called maximum matching, is to find a matching with the greatest number of nodes. Unlike the assignment problem, the maximum matching problem is NP-complete. [HG99]
katte ülesanne 
Kate on antud graafi alamgraaf, mille suvalised kaks serva ei ole intsidentsed sama tipuga. Ülesandeks on teatud kitsendusi arvestades leida lubatud kate, mis optimeerib mingit sihifunktsiooni (nt kattesse kuuluvate servade kaalude summat). Täiusliku katte puhul on iga tipp intsidentne täpselt ühe servaga. 

Määramisülesande lahend on klassikaline täiuslik kate, kus graaf on bikromaatiline (tippudeks on kaks hulka – inimesed ja töökohad) ning kattesse peavad kuuluma kõik tipud (igal inimesel peab olema töökoht ja kõik töökohad tuleb täita). Seega vastab kate täpselt määramisele, kuna iga töökoha tipp on intsidentne täpselt ühe inimese tipuga. Lisaks võrdub iga sellise katte koguhind vastava määramise koguhinnaga, mistõttu minimaalse katte ülesanne on ekvivalentne määramisülesandega. 
Teist tüüpi ülesandes, maksimumkatte ülesandes, tuleb leida suurima tippude arvuga kate. Erinevalt määramisülesandest on maksimumkatte ülesanne 
NP-täielik.
matchstick graph
A planar graph whose edges are all unit line segments. [EW00] 
tuletikkgraaf = tuletikk
Planaarne graaf, mille servad on ühesugused joonelõigud.
matrix
An array of symbols arranged in rows and columns. [HC00]
FIGURE
 maatriks
Ridadesse ja veergudesse paigutatud sümbolite massiiv.
JOONIS
matrix tree theorem
The number of spanning trees of a graph on n vertices is the (absolute value of the) determinant of any (n – 1) by (n – 1) submatrix of the augmented adjacency matrix. [SL99]
If G is a nontrivial labelled graph with adjacency matrix A and degree matrix D , then the number of distinct spanning trees of G is the value of any cofactor of the matrix D – A . [CL96] 
täispuude arvu maatriksteoreem
n tipuga graafi täispuude arv võrdub laiendatud naabrusmatriksi suvalise (n – 1) ´ (n – 1) alammaatriksi determinandiga (või selle absoluutväärtusega).
Olgu G mittetriviaalne märgendatud graaf naabrusmaatriksiga A ja astmemaatriksiga D . Graafi G erinevate täispuude arv võrdub maatriksi D – A suvalise algebralise täiendi väärtusega.
matroid
Let E = {e1 , e2 , ... , em} be a finite set, and let F be a family of subsets of E: then F is a matroid if it satisfies 
  • ei in F for each i ; 
  • if G is in F, and if H is a non-empty subset of G, then H is in F ; 
  • for each S that is a subset of E, if G and H are two members of F contained in S and maximal with this property, then | G | = | H | . 

    • [ODC00]
    There are many definitions of matroids. A matroid M = (S, I) is a finite set S , together with a collection of subsets I of S such that
  • the empty set is in I ; 
  • if X is in I, then any subset of X is in I ; and 
  • if X and y are in I with | Y | > | X | , then there is some element y in Y \ X such that XÈ {y} is in I . 
    • [SL99] 
    		 matroid 
    Olgu E = {e1 , e2 , ... , em} lõplik hulk ja F hulga E alamhulkade pere. F on matroid, kui kehtivad järgmised tingimused: 
  • iga i puhul ei Î F ; 
  • kui G Î F ja H on G mittetühi alamhulk, siis 

    • H Î F ; 
  • kui iga S Í E puhul G ÍS ja H Í S on pere F liikmed, rahuldavad seda omadust ja on maksimaalsed, siis | G | = | H | .


    • On olemas mitmesuguseid matroidi definitsioone. Matroid M = (S, I) on lõplik hulk S koos alamhulkade I ÍS kogumiga, kusjuures: 
  • hulk I sisaldab tühihulka; 
  • kui hulk X kuulub hulka I , siis iga hulga X alamhulk kuulub hulka I ; 
  • kui X ja Y kuuluvad hulka I ning | Y | > | X | , siis leidub element y ÎY \ X , nii et X È {y} kuulub hulka I .
    		•
    matroid basis graph
    Graph whose vertex set is the collection of bases of a matroid, adjacent when their symmetric difference has two elements. [DW96]
    matroidi baasigraaf
    Graaf, mille tippude hulk vastab matroidi baaside kogumile, kusjuures tipud on intsidentsed siis, kui baaside sümmeetriline vahe sisaldab kahte elementi.
    matroid covering theorem
    The number of independent sets needed to cover the elements of a matroid is max X Í Eé|X |û  . [DW96]
    matroidi katmise teoreem
    Matroidi elementide katmiseks vajalike sõltumatute hulkade arv on max XÍ E é|X |û  .
    matroid intersection theorem
    The maximum size of a common independent set in two matroids on E equals the minimum over X Í E of the rank of X in the first matroid plus the rank of X' in the second matroid. [DW96]
    matroidide ühisosa teoreem
    Hulgal E defineeritud kahe matroidi ühise sõltumatu hulga maksimumsuurus võrdub alamhulga X Í E miinimumastak esimeses matroidis pluss alamhulga X' astak teises matroidis.
    matroid packing theorem
    The maximum number of pairwise disjoint bases in a matroid is min r(X) < r(E) ë (|E | –CA(X)) / (r(E) – r(X))û . 
    [DW96]
    matroidi pakkimisteoreem
    Matroidi paariviisi ühisosata baaside maksimumarv on min r(X) < r(E) ë (| E | – CA(X)) / (r(E) – r(X))û .
    matroid rank function
    A polymatroid rank function that takes integral values and does not exceed 1 on any of the singletons. [HN97]
    matroidi astakufunktsioon
    Polümatroidi astakufunktsioon, mille väärtused on täisarvulised ja ei ole ühegi üksikelemendi puhul suuremad kui 1.
    matroid union theorem
    The union of matroids M1, …, Mk is a matroid with rank function r(X) = min Y Í X (| X – Y | + Sri(Y)) .[DW96]
    matroidide ühendi teoreem
    Matroidide M1, …, Mk ühend on matroid astakufunktsiooniga 

    r(X) = min Y Í X (| X – Y | + Sri(Y)) .
    max cut problem
    Given a graph G = (V, E) , weight w(e) ÎZ+for eache ÎEand positive integer K , is there a partition of V into disjoint sets V1 and V2 such that the sum of the weights of the edges from E that have one endpoint in V1 and one endpoint in V2 is at least K ? [GJ79]
    maksimumlõike ülesanne
    Antud on graaf G = (V, E) , servade eÎEkaalud 

    w(e) Î Z+ja positiivne täisarv K . Kas leidub hulga V tükeldus ühisosata hulkadeks V1 ja V2 , nii et servade, mille üks otspunkt asub hulgas V1 ja teine hulgas V2 , kaalude summa on vähemalt K ?
    max flow problem 
    In a network, [V, A] , there are two special nodes in V: a source (s) and a sink (t). The problem is to maximize the flow from s to t subject to conservation of flow constraints at each node and flow bounds on each arc. [HG99]
    maksimumvoo ülesanne 
    Antud on võrk [V, A] ning kaks spetsiaaltippu s (allikas) ja t (neel). Leida maksimumvoog tipust s tippu t , arvestades jäävustingimusi tippudes ja läbilaskekitsendusi kaartes.
    max-flow min-cut theorem = maximum flow, minimum cut theorem
    In a transport network, the value of any maximal flow is equal to the capacity of any minimal cut. [HC00]
    The maximum flow through a (single commodity) capacitated network from a specified node, called the source, to another node, called the sink, equals the value of the minimum cutset. Originally proven directly from principles of networks, this was discovered to be a special case of the Duality Theorem of Linear Programming. [HG99]
    The maximum flow between vertices vi and vj in a graph G is exactly the weight of the smallest set of edges to disconnect G with vi and vj in different components. [EW00]
    maksimumvoo ja miinimumlõike teoreem 

    Transpordivõrgus võrdub suvaline maksimumvoog mistahes miinmumlõike läbilaskevõimega.
    Läbilaskevõimetega ühekaubavõrgus võrdub maksimumvoog kindlast tipust (allikast) teise kindlasse tippu (neelu) miimumlõike väärtusega. Tõestati esialgselt võrguteoorias, hiljem osutus lineaarplaanimise duaalsusteoreemi erijuhuks.


    Maksimumvoog graafi G tippude vi ja vj vahel võrdub täpselt vähima servade hulga kogukaaluga, mis tükeldab graafi G , nii et tipud vi ja vj asuvad eri komponentides.
    max-heap property
    Each node in a tree has a key which is less than or equal to the key of its parent. [PEB00]
    maksimumkuhiku omadus
    Puu igal tipul on võti, mis on väiksem ematipu võtmest või sellega võrdne.
    maximal clique 
    A maximal vertex set inducing a clique. [DW96]
    maksimumklikk 
    Maksimaalne tipuhulk, mis sisaldab klikki.
    maximal connected subgraphs
    A set of connected subgraphs g1 , g2 , … , gr such that every edge and every vertex in G is exactly in one of these subgraphs where an isolated vertex is a connected subgraph by definition. [WM72]
    maksimaalsed sidusad alamgraafid
    Sidusate alamgraafide hulk g1 , g2 , … , gr , nii et graafi G iga serv ja iga tipp kuuluvad täpselt ühte nendest alamgraafidest, kusjuures isoleeritud tipp on definitsiooni järgi sidus alamgraaf.
    maximal cycle
    A simple cycle surrounding whole graph.
    maksimumtsükkel
    Kogu graafi piirav elementaartsükkel. [OO76]
    JOONIS
    maximal flow
    A feasible flow in a network whose value is as large as possible. [BC79]
    maksimumvoog
    Lubatud voog võrgus, mille väärtus on nii suur kui võimalik.
    maximal independent vertex set
    An independent vertex set is called maximal if it is not contained in any larger independent set. [RND77]
    A set of vertices in a graph such that for any pair of vertices, there is no edge between them and such that no more vertices can be added and it still be an independent set. [PEB00]
    maksimaalne sõltumatu tipuhulk
    Sõltumatu tipuhulk on maksimaalne, kui see ei sisaldu üheski suuremas sõltumatus hulgas.
    Graafi tippude hulk, kus suvaline tipupaar pole ühendatud servaga ning millele ei saa lisada ühtegi tippu, nii et hulk jääks sõltumatuks.
    JOONIS
    maximal path = maximal trail 
    Non-extendible path or trail. [DW96]
    maksimumtee = maksimumrada 
    Mittelaiendatav tee või rada.
    JOONIS
    maximal planar graph = triangulation
    maksimaalne planaarne graaf = triangulatsioon
    maximal P-object
    For a property P, no object of the same type properly containing this object also has property P. [DW96]
    maksimaalne P-objekt
    Objekt, mis ei sisaldu üheski teises sama tüüpi objektis, millel on atribuut P .
    maximal trail = maximal path
    maksimumrada = maksimumtee 
    maximum cardinality search 
    An algorithm for recognizing chordal graphs. [DW96]
    maksimumvõimsusega otsing 
    Algoritm kõõlgraafide tuvastamiseks.
    maximum achromatic number 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A complete coloring of G , i.e., a partition of V into disjoint sets V1 , V2 , … , Vk such that each Vi is an independent set for G and such that, for each pair of distinct sets Vi and Vj , Vi ÈVjis not an independent set. 
    MEASURE: Cardinality of the complete coloring, i.e., the number of disjoint independent sets Vi . [CK00]
    maksimaalne akromaatiline arv 
    VARIANT: graaf G = (V, E) . 
    LAHEND: graafi G täielik värving, st hulga V tükeldus ühisosata alamhulkadeks V1 , V2 , … , Vk , nii et iga Vi on G sõltumatu hulk ning ükski ühisosata hulkade paar Vi ja Vj , Vi ÈVj , ei ole sõltumatu hulk. 
    MÕÕT: täieliku värvingu võimsus, st ühisosata sõltumatute hulkade Vi arv.
    maximum balanced connected partition
    INSTANCE: Connected graph G = (V, E) , nonnegative vertex-weight function w : V ®N . 
    SOLUTION: A partition (V1 , V2) of V into nonempty disjoint sets V1 and V2 such that the subgraphs of G induced by V1 and V2 are connected. 
    MEASURE: Balance of the partition, i.e., 

    min {w(V1) , w(V2)} where w( V' ) = S v Î V ' w(v) . [CK00]
    maksimaalne tasakaalustatud sidus tükeldus
    VARIANT: sidus graaf G = (V, E) , tippude mittenegatiivne kaalufunktsioon w : V ®N . 
    LAHEND: hulga V tükeldus (V1 , V2) mittetühjadeks ühisosata hulkadeks V1 ja V2 , nii et V1 ja V2 tekitatud graafi G alamgraafid on sidusad. 
    MÕÕT: tükelduse tasakaal, st min {w(V1) , w(V2)} , kus w( V' ) = S v Î V 'w(v) .
    maximum clique 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A clique in G , i.e. a subset V' ÍVsuch that every two vertices in V' are joined by an edge in E . 
    MEASURE: Cardinality of the clique | V' | . [CK00]
    A clique of maximum order in G . [BW97]
    maksimumklikk 
    VARIANT: graaf G = (V, E) . 
    LAHEND: graafi G klikk, st alamhulk V' ÍV , nii et hulga V' suvalised kaks tippu on ühendatud hulka E kuuluva servaga. 
    MÕÕT: kliki võimsus | V' | .
    Graafi G maksimumjärguga klikk.
    maximum clique problem = party problem
    Given a graph G and a positive integer 

    K , does the largest complete subgraph in G contain exactly K vertices? [GJ79]
    Find the minimum number of guests that must be invited so that at least m will know each other or at least n will not know each other. The solutions are known as Ramsey numbers. [EW00] 
    maksmumkliki ülesanne = võõruspeo ülesanne
    Antud on graaf G ja positiivne täisarv K . Kas graafi G suurim täielik alamgraaf sisaldab täpselt K tippu?

    Leida kutsutavate külaliste miinimumarv, nii et vähemalt m külalist oleksid üksteisega tuttavad või vähemalt n külalist ei tunneks üksteist. Lahendid on tuntud kui Ramsey arvud.
    maximum common embedded subtree 
    INSTANCE: Trees T1 and T2 with labels on the nodes. 
    SOLUTION: A common embedded sub-tree, i.e. a labeled tree T ' that can be embedded into both T1 and T2 . An embedding from T ' to T is an injective function from the nodes of T ' to the nodes of T that preserves labels and ancestorship. Note that since fathership does not need to be preserved, T ' does not need to be an ordinary subtree. 
    MEASURE: Cardinality of the common embedded sub-tree | T ' | . [CK00]
    maksimaalne ühine kujutatud alampuu 
    VARIANT: märgendatud tippudega puud T1 ja T2 . 

    LAHEND: ühine kujutatud alampuu, st märgendatud puu T ' , mida saab kujutada nii puul T1 kui ka puul T2. Puu T ' kujutus puule T on injektiivne funktsioon puu T ' tippudelt puu T tippudele, mis säilitab märgendid ja eellasseosed. Kuna emadusseosed ei pea säilima, siis ei pruugi T ' olla tavaline alampuu. 
    MÕÕT: ühise kujutatud alampuu võimsus | T ' | .
    maximum common induced subgraph 
    INSTANCE: Graphs G1 = (V1, E1) and 

    G2 = (V2, E2) .
    SOLUTION: A common induced subgraph, i.e. subsets V1' ÍV1 and V2' ÍV2 such that | V1' | = | V2' | , and the subgraph of G1 induced by V1' and the subgraph of G2 induced by V2' are isomorphic. 
    MEASURE: Cardinality of the common induced subgraph | V1' | . [CK00]
    maksimaalne ühine tekitatud alamgraaf 
    VARIANT: graafid G1 = (V1, E1) ja G2 = (V2, E2) .

    LAHEND: ühine tekitatud alamgraaf, st alamhulgad V1' ÍV1 ja V2' ÍV2 , | V1' | = | V2' | , nii et hulga V1' tekitatud graafi G1 alamgraaf ja hulga V2' tekitatud graafi G2 alamgraaf on isomorfsed. 
    MÕÕT: ühise tekitatud alamgraafi võimsus | V1' | .
    maximum common subgraph 
    INSTANCE: Graphs G1 = (V1, E1) and 

    G2 = (V2, E2) .
    SOLUTION: A common subgraph, i.e. subsets 

    E1' Í E1 and E2' Í E2 such that the two subgraphs 
    G1' = (V1, E1') and G2' = (V1, E2') are isomorphic. 
    MEASURE: Cardinality of the common subgraph 

    | E' | . [CK00]
    maksimaalne ühine alamgraaf 
    VARIANT: graafid G1 = (V1, E1) ja G2 = (V2, E2) . 

    LAHEND: ühine alamgraaf, st alamhulgad E1' ÍE1 ja E2' ÍE2 , nii et kaks alamgraafi G1' = (V1, E1') ja G2' = (V1, E2') on isomorfsed. 
    MÕÕT: ühise alamgraafi võimsus | E' | .
    maximum common subtree 
    INSTANCE: Collection T1 , … , Ti of trees. 
    SOLUTION: A tree T' isomorphic to a subtree (i.e. induced connected subgraph) of each Ti . 
    MEASURE: Size, i.e. number of nodes, of the common subtree T' . [CK00]
    maksimaalne ühine alampuu 
    VARIANT: puude kogum T1 , … , Ti . 
    LAHEND: iga puu Ti alampuuga (st tekitarud sidusa alamgraafiga) isomorfne puu T' . 
    MÕÕT: ühise alampuu T' suurus (tippude arv).
    maximum cut 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A partition of V into disjoint sets V1 and V2 . 
    MEASURE: The cardinality of the cut, i.e., the number of edges with one end point in V1 and one endpoint in V2 . [CK00]
    maksimumlõige 
    VARIANT: graaf G = (V, E) . 
    LAHEND: hulga V tükeldus ühisosata hulkadeks V1 ja V2 . 
    MÕÕT: lõike võimsus, st servade arv, mille üks otspunkt on hulgas V1 ja teine hulgas V2 .
    maximum degree-bounded connected subgraph 
    INSTANCE: Graph G = (V, E) , a weight function 

    w : E ® N , and an integer d ³ 2 .
    SOLUTION: A subset E' Í E such that the subgraph G' = (V, E' ) is connected and has no vertex with degree exceeding d . 
    MEASURE: The total weight of the subgraph 

    S e Î E ' w(e) . [CK00]
    maksimaalne astmekitsendusega sidus alamgraaf
    VARIANT: graaf G = (V, E) , kaalufunktsioon

    w : E ® N ja täisarv d³ 2 .
    LAHEND: alamhulk E' Í E , mille puhul alamgraaf 

    G' = (V, E' ) on sidus ja ei sisalda tippu, mille aste oleks suurem kui d . 
    MÕÕT: alamgraafi kogukaal S e Î E ' w(e) .
    maximum degree
    The maximum degree among the vertices of G. [CL96] 
    maksimumaste
    Graafi G tippude maksimumaste.
    maximum directed cut 
    INSTANCE: Directed graph G = (V, A) . 
    SOLUTION: A partition of V into disjoint sets V1 and V2 . 
    MEASURE: The cardinality of the cut, i.e., the number of arcs with one end point in V1 and one endpoint in V2 . [CK00] 
    maksimaalne orienteeritud lõige 
    VARIANT: orienteeritud graaf G = (V, A) . 
    LAHEND: Hulga V tükeldus ühisosata hulkadeks V1 ja V2 . 
    MÕÕT: lõike võimsus, st kaarte arv, mille üks otspunkt on on hulgas V1 ja teine hulgas V2 .
    maximum disjoint connecting paths 
    INSTANCE: Multigraph G = (V, E) , collection of vertex pairs T = {(s1 , t1), (s2 , t2), … , (si , ti)} . 
    SOLUTION: A collection of edge disjoint paths in G connecting some of the pairs (si , ti) , i.e. sequences of vertices u1 , u2 , … , um such that, for some i , ui = si , um = ti , and for any j , (uj , uj+1) ÎE . 
    MEASURE: The number of vertex pairs (si , ti) that are connected by the paths. [CK00]
    maksimaalsed ühisosata ühendusteed 
    VARIANT: multigraaf G = (V, E) ja tipupaaride kogum T = {(s1 , t1), (s2 , t2), … , (si , ti)} . 
    LAHEND: teatud tipupaare (si , ti) ühendavate ühisservadeta teede kogum graafis G , st tippude jadad u1 , u2 , … , um , nii et teatud i puhul ui = si , 

    um = ti ja teatud j puhul (uj , uj+1) ÎE . 
    MÕÕT: tipupaaride (si , ti) arv, mida teed ühendavad.
    maximum domatic partition 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A partition of V into disjoint sets 

    V1 , V2 , … , Vksuch that each Vi is a domatinating set of G . 
    MEASURE: Cardinality of the partition, i.e., the number of disjoint subsets Vi . [CK00]
    maksimaalne dominantsustükeldus 
    VARIANT: graaf G = (V, E) . 
    LAHEND: hulga V tükeldus ühisosata hulkadeks 

    V1 , V2 , … , Vk , nii et iga Vi on graafi G dominanthulk. 
    MÕÕT: tükelduse võimsus, st ühisosata alamhulkade Vi arv.
    maximum edge subgraph 
    INSTANCE: Graph G = (V, E) , a weight function 

    w : E ® N , and positive integer k .
    SOLUTION: A subset V' Í V such that | V' | = k . 
    MEASURE: Total weight of the edges in the subgraph induced by V' , i.e. S (u, v) Î E Ç (V ' ´ V ')w(u, v) . [CK00] 
    servade maksimaalse kogukaaluga alamgraaf 
    VARIANT: graaf G = (V, E) , kaalufunktsioon 

    w : E ® N ja positiivne täisarv k . 
    LAHEND: alamhulk V' Í V , | V' | = k . 
    MÕÕT: hulga V' tekitatud alamgraafi servade kogukaal S(u, v) Î E Ç (V ' ´ V ') w(u, v) .
    maximum facility location 
    INSTANCE: Complete graph G = (V, E) , costs 

    c(vi , vj) ÎN that are symmetric and satisfy the triangle inequality, set of locations FÍV where a facility may be built, for each vÎF a nonnegative cost f(v) of building a facility at v , for each location 
    v Î V a nonnegative demand d(v) .
    SOLUTION: Locations for the facilities to be built 

    F' Í F . 
    MEASURE: 

    S v Î F ' f(v) + S u Î F ' S v Î V d(v) c( f1 , f 2) . [CK00]
    rajatiste optimaalne asukoht 
    VARIANT: täielik graaf G = (V, E) , hinnad 

    c(vi , vj) ÎN (sümmeetrilised, rahuldavad kolmnurga võrratust), asukohtade hulk FÍV rajatise ehitamiseks, mittenegatiivne hind f(v) rajatise ehitamiseks tippu v ÎF , mittenegatiivne nõudlus d(v) iga asukoha vÎV jaoks. 
    LAHEND: asukohad F' Í F rajatiste ehitamiseks. 
    MÕÕT: 
    S v Î F ' f(v) + S u Î F ' S v Î V d(v) c( f1 , f 2) .
    maximum fixed-length disjoint paths problem

    Given a graph G = (V, E) , specified vertices s and t , positive integers J , K £ | V | , does G contain J or more mutually vertex-disjoint paths from s to t , each involving exactly K edges? [GJ79]
    ühepikkuste ühistippudeta teede maksimumarvu ülesanne
    Antud on graaf G = (V, E) , kindlad tipud s ja t ning positiivsed täisarvud J , K £ | V | . Kas graaf G sisaldab J või enam paariviisi ühistippudeta teed tipust s tippu t , mille pikkus on täpselt K serva?
    maximum flow 
    A feasible network flow of maximum value , or the value itself. [DW96]
    maksimumvoog 
    Maksimumväärtusega lubatud voog võrgus või see väärtus ise.
    maximum flow, minimum cut theorem = max-flow min-cut theorem
    maksimumvoo ja miinimumlõike teoreem
    maximum flow problem
    The problem of finding the maximum flow between any two vertices of a graph. [PEB00]
    maksimumvoo ülesanne
    Maksimumvoo leidmise ülesanne graafi kahe suvalise tipu vahel.
    maximum frequency allocation 
    INSTANCE: Graph G = (V, E) , and, for each node u , a finite set L(u) Ì Z+ of available frequencies and an integer Mu . 
    SOLUTION: A frequency allocation for G , i.e., for each node u , a subset S(u) of L(u) such that, for all 

    u Î V , 1 £ | S(u) | £Mu , and, for all (u, v)Î E , 
    S(u) Ç S(v) = 0 . 
    MEASURE: The stability number of the allocation 

    S u Î V | S(u) | . [CK00]
    maksimaalne sagedusjaotus 
    VARIANT: graaf G = (V, E) , igas tipus u saadaolevate sageduste lõplik hulk L(u) ÌZ+ ja täisarv Mu . 
    LAHEND: sagedusjaotus graafil G , st iga tipu u jaoks hulga L(u) alamhulk S(u) , nii et kõigi u Î V puhul 1 £ | S(u) | £Mu ja kõigi (u, v)ÎE puhul 

    S(u) Ç S(v) = 0 .
    MÕÕT: jaotuse stabiilsustegur S u Î V | S(u) | .
    maximum H-matching 
    INSTANCE: Graph G = (VG , EG) and a fixed graph H = (VH , EH) with at least three vertices in some connected component. 
    SOLUTION: A H-matching for G , i.e., a collection of disjoint subgraphs G1 , G2 , … , Gk of G , each isomorphic to H . 
    MEASURE: Cardinality of the H-matching, i.e., the number of disjoint subgraphs Gi . [CK00]
    maksimaalne H-kate 
    VARIANT: graaf G = (VG , EG) ja fikseeritud graaf

    H = (VH , EH) , mille vähemalt kolm tippu asuvad mõnes sidusas komponendis. 
    LAHEND: graafi G H-kate, st graafi G ühisosata alamgraafide kogum G1 , G2 , … , Gk , igaüks isomorfne graafiga H . 
    MÕÕT: H-katte võimsus, st ühisosata alamgraafide Gi arv.
    maximum independent sequence 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: An independent sequence for G , i.e., a sequence v1 , … , vm of independent vertices of G such that, for all i < m , a vertex v'iÎV exists which is adjacent to vi+1 but is not adjacent to any vj for j £i . 
    MEASURE: Length of the sequence m . [CK00]
    maksimaalne sõltumatu jada 
    VARIANT: graaf G = (V, E) . 
    LAHEND: graafi G sõltumatu jada, st graafi G sõltumatute tippude jada v1 , … , vm , nii et kõigi i < m puhul leidub tipp v'iÎV , mis on intsidentne tipuga vi+1 , kuid ei ole intsidentne ühegi tipuga vj , j £i . 

    MÕÕT: jada pikkus m .
    maximum independent set 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: An independent set of vertices, i.e. a subset V'ÍV such that no two vertices in V' are joined by an edge in E . 
    MEASURE: Cardinality of the independent set | V' | . [CK00]
    maksimaalne sõltumatu hulk 
    VARIANT: graaf G = (V, E) . 
    LAHEND: tippude sõltumatu hulk, st alamhulk 

    V' Í V , mille puhul hulga V' kaks tippu on ühendatud hulka E kuuluva servaga. 
    MÕÕT: sõltumatu hulga võimsus | V' | .
    maximum induced connected subgraph with property P
    INSTANCE: Graph G = (V, E) .
    SOLUTION: A subset V' Í V such that the subgraph induced by V' is connected and has the property P . 
    MEASURE: Cardinality of the induced connected subgraph | V' | . [CK00]    		 maksimaalne tekitatud sidus alamgraaf 
    omadusega P
    VARIANT: graaf G = (V, E) .
    LAHEND: alamhulk V' Í V , mille puhul hulga V' tekitatud alamgraaf on sidus ja omadusega P . 
    MÕÕT: tekitatud sidusa alamgraafi võimsus | V' | .
    maximum induced subgraph with property P 
    INSTANCE: Graph G = (V, E) . The property P must be hereditary, i.e., every subgraph of G' satisfies P whenever G' satisfies P , and non-trivial, i.e., it is satisfied for infinitely many graphs and false for infinitely many graphs. 

    SOLUTION: A subset V' Í V such that the subgraph induced by V' has the property P . 
    MEASURE: Cardinality of the induced subgraph 

    | V' | . [CK00]
    		 maksimaalne tekitatud alamgraaf omadusega P
    VARIANT: graaf G = (V, E) . Omadus P peab olema pärilik, st kui graaf G' rahuldab omadust P , siis rahuldab omadust P ka graafi G' iga alamgraaf. Teiste sõnadega, omadus kehtib lõpmatult paljude graafide puhul ja ei kehti lõpmatult paljude graafide puhul. 
    LAHEND: alamhulk V' Í V , mille puhul hulga V' tekitatud alamgraafil on omadus P . 
    MÕÕT: tekitatud alamgraafi võimsus | V' | .
    maximum integral k-multicommodity flow on trees 
    INSTANCE: A tree T = (V, E) , a capacity function c : E ® N and k pairs of vertices (si , ti) . 
    SOLUTION: A flow fi for each pair (si , ti) with fi ÎN such that, for each e Î E ,Si=1 kfi qi (e) £c(e) where qi (e) = 1 if e belongs to the unique path from si to ti , and qi (e) = 0 otherwise. 
    MEASURE: The sum of the flows S i=1 kfi . [CK00]
    maksimaalne täisarvuline k-kaubavoog puudel 

    VARIANT: puu T = (V, E) , läbilaskefunktsioon
    c : E ® N ja k tipupaari (si , ti) .
    LAHEND: iga paari (si , ti) jaoks voog fiÎN , nii et e Î E puhul Si=1 kfi qi (e) £c(e) , kus qi (e) = 1 , kui e kuulub ühesesse teesse tipust si tippu ti , ja 

    qi (e) = 0 muul juhul. 
    MÕÕT: voogude summa S i=1 kfi .
    maximum k-colorable induced subgraph 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A subset V' Í V such that the induced subgraph G' = (V', E' ) is k-colorable, i.e., there is a coloring for G' of cardinality at most k . 
    MEASURE: Cardinality of the vertex set of the induced subgraph | V' | . [CK00]
    maksimaalne k-värvitav tekitatud alamgraaf 
    VARIANT: graaf G = (V, E) . 
    LAHEND: alamhulk V' Í V , mille puhul tekitatud alamgraaf G' = (V', E' ) on k-värvitav, st leidub graafi G' värving võimsusega vähemalt k . 
    MÕÕT: tekitatud alamgraafi tippude hulga võimsus 

    | V' | .
    maximum k-colorable subgraph 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A subset E' Í E such that the subgraph G' = (V, E' ) is k-colorable, i.e., there is a coloring for G' of cardinality at most k . 
    MEASURE: Cardinality of the subgraph | E' | . [CK00]
    maksimaalne k-värvitav alamgraaf 
    VARIANT: graaf G = (V, E) . 
    LAHEND: alamhulk V' Í V , mille puhul tekitatud alamgraaf G' = (V', E' ) on k-värvitav, st leidub graafi G' värving võimsusega vähemalt k . 
    MÕÕT: alamgraafi võimsus | E' | .
    maximum k-cut 
    INSTANCE: Graph G = (V, E) , a weight function 

    w : E ® N , and an integer k Î [ 2 … | V | ] .
    SOLUTION: A partition of V into k disjoint sets 

    F = { C1 , C2 , … , Ck } . 
    MEASURE: The sum of the weight of the edges between the disjoint sets 

    S 1 k-1 Si+1 kSv1 ÎC i , v2 ÎC jw({v1, v2}) . [CK00]
    maksimaalne k-lõige 
    VARIANT: graaf G = (V, E) , kaalufunktsioon

    w : E ® N ja täisarv kÎ [ 2 … | V | ] . 
    LAHEND: hulga V tükeldus k ühisosata hulgaks 

    F = { C1 , C2 , … , Ck } .
    MÕÕT: ühisosata hulkade vaheliste servade kaalude summa S1 k-1Si+1 kSv1 ÎC i , v2 ÎC jw({v1, v2}) .
    maximum k-facility dispersion 
    INSTANCE: Complete graph G = (V, E) and distances d(vi , vj) ÎN satisfying the triangle inequality. 
    SOLUTION: A set of k facilities, i.e., a subset F ÍV with | F | = k . 
    MEASURE: The minimum distance between two facilities min f1 , f2 Î F d( f1 , f 2) . [CK00] 
    k rajatise maksimumdispersioon 
    VARIANT: täielik graaf G = (V, E) ja kaugused 

    d(vi , vj) ÎN , mis rahuldavad kolmnurga võrratust. 
    LAHEND: k rajatise hulk, st alamhulk F ÍV , 

    | F | = k .
    MÕÕT: kahe rajatise vaheline miinimumkaugus 

    min f1 , f2 Î F d( f1 , f 2) .
    maximum k-facility location 
    INSTANCE: Complete graph G = (V, E) and profits p(vi , vj) ÎN . 
    SOLUTION: A set of k facilities, i.e., a subset F ÍV with | F | = k . 
    MEASURE: The maximum total profit 

    S v Î V max f Î F p(v, f) . [CK00]
    k rajatise optimaalne paigutus 
    VARIANT: täielik graaf G = (V, E) ja kasumid

    p(vi , vj) ÎN . 
    LAHEND: k rajatise hulk, st alamhulk F ÍV , 

    | F | = k . 
    MÕÕT: maksimaalne kogukasum 

    S v Î V max f Î F p(v, f) .
    maximum leaf spanning tree 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A spanning tree for G . 
    MEASURE: The number of leaves of the spanning tree. [CK00]
    maksimaalse lehtede arvuga täispuu 
    VARIANT: graaf G = (V, E) . 
    LAHEND: graafi G täispuu. 
    MÕÕT: täispuu lehtede arv.
    maximum leaf spanning tree problem
    Given a graph G = (V, E) and positive integer 

    K £ | V | , is there a spanning tree for G in which K or more vertices have degree 1 ? [GJ79]
    maksimaalse lehtede arvuga täispuu ülesanne
    Antud on graaf G = (V, E) ja positiivne täisarv 

    K £ | V | . Kas leidub graafi G täispuu, kus on K või enam tippu astmega 1 ?
    maximum length-bounded disjoint paths problem

    Given a graph G = (V, E) , specified vertices s and t , positive integers J , K £ | V | , does G contain J or more mutually vertex-disjoint paths from s to t , none involving more than K edges? [GJ79]
    piiratud maksimumpikkusega ühisosata teede ülesanne
    Antud on graaf G = (V, E) , kindlad tipud s ja t ning positiivsed täisarvud J , K £ | V | . Kas graaf G sisaldab J või enam paariviisi ühistippudeta teed tipust s tippu t , nii et üheski tees pole üle K serva?
    maximum matching
    A matching of maximal cardinality. [CL96]
    maksimumkate
    Maksimumvõimsusega kate.
    maximum minimum metric k-spanning tree 
    INSTANCE: Graph G = (V, E) , length l(e) ÎNfor each e ÎE satisfying the triangle inequality. 

    SOLUTION: A subset V ' Í V such that | V ' | = k . 
    MEASURE: Cost of the minimum spanning tree of the subgraph induced by V' .[CK00]
    maksimaalne miinimummeetrikaga k-täispuu 
    VARIANT: graaf G = (V, E) , servade eÎE pikkused l(e) Î N , mis rahuldavad kolmnurga võrratust. 
    LAHEND: alamhulk V ' Í V , | V ' | = k . 
    MÕÕT: hulga V' tekitatud alamgraafi minimaalse täispuu hind.
    maximum minimum spanning tree deleting k edges 
    INSTANCE: Graph G = (V, E) and a weight function w : E ® N . 
    SOLUTION: Subset E ' Í E of k edges and a minimum spanning tree T in the graph (V, E – E' ) . 
    MEASURE: Weight of T . [CK00]
    k serva kustutamisega maksimaalne miinimumtäispuu 
    VARIANT: graaf G = (V, E) ja kaalufunktsioon 

    w : E ® N . 
    LAHEND: k serva alamhulk E ' ÍE ja graafi 

    (V, E – E' ) miinimumtäispuu T . 
    MÕÕT: puu T kaal.
    maximum planar subgraph 
    INSTANCE: Graph G = (V, E) . 
    SOLUTION: A subset E' Í E such that G' = (V, E' ) is planar. 
    MEASURE: Size of the subset | E' | . [CK00]
    maksimaalne planaarne alamgraaf 
    VARIANT: graaf G = (V, E) . 
    LAHEND: alamhulk E' Í E , mille puhul graaf 

    G' = (V, E' ) on planaarne. 
    MÕÕT: alamhulga suurus | E' | .
    maximum P-object 
    For a property P, no larger object of the same type also has property P. [DW96]
    maksimaalne P-objekt 
    Objekt, millest pole ühtki suuremat sama tüüpi objekti atribuudiga P.
    maximum priority flow 
    INSTANCE: Directed graph G = (V, E) , sources 

    s1 , … , sk ÎV , sinks t1 , … , tk ÎV , a capacity function c : E ®R , a bound function b : V ®R , and, for any vertex v , a partial order on the set of edges leavingv . 
    SOLUTION: A priority flow f , i.e., a function f : E®R such that 
  • for any edge e , f(e) £c(e) , 
  • for any vertex v Î V – { s1 , … , sk , t1 , … , tk} the flow is conserved at v , 
  • for any vertex v , the flow leaving v is at most b(v), and 
  • for any vertex v and for any pair of edges e1 , e2 leaving v , if f(e1) <c(e2) and e1 is less than e2 , then f(e2) = 0 . 
    • MEASURE: The amount of flow entering sink t1 , i.e., S(x , t1)Î E f(x, t1) . [CK00]
    maksimaalne eelisvoog 
    VARIANT: orienteeritud graaf G = (V, E) , allikad 

    s1 , … , sk ÎV , neelud t1 , … , tk ÎV , läbilaskefunktsioon c : E ®R , tõkkefunktsioon 
    b : V ® R ja iga tipu v jaoks tipust väljuvate servade osaline järjestus. 
    LAHEND: eelisvoog f , st funktsioon f : E ®R , mille puhul 
  • suvalise serva e jaoks f(e) £c(e) , 
  • suvalises tipus v Î V – { s1 , … , sk , t1 , … , tk} voog konserveeritakse, 
  • suvalisest tipust v väljuv voog ei ületa väärtust b(v) , 
  • suvalise tipu v ja sellest väljuva suvalise servapaari e1 , e2 puhul kui f(e1) <c(e2) ja e1 on väiksem kui e2 , siis f(e2) = 0 . 
    • MÕÕT: neelu t1 suubuvate voogude summa 

    S (x , t1)Î E f(x, t1) .
    maximum subforest 
    INSTANCE: Tree G = (V, E) and a set of trees H . 
    SOLUTION: A subset E' Í E such that the subgraph G' = (V, E' ) does not contain any subtree isomorphic to a tree from H . 
    MEASURE: Cardinality of the subgraph | E' | . [CK00]
    maksimaalne alammets 
    VARIANT: puu G = (V, E) ja puude hulk H . 
    LAHEND: alamhulk E' Í E , mille puhul alamgraaf 

    G' = (V, E' ) ei sisalda hulka H kuuluva puuga isomorfset alampuud. 
    MÕÕT: alamgraafi võimsus | E' | .
    maximum subgraph matching problem
    Given digraphs G = (V1 , A1) , H = (V2 , A2) and positive integer K , is there a subset R ÍV1´V2 with | R | ³K such that for all <u, u'> , <v, v'> ÎR , (u, v) ÎA1 if and only if ( u ', v ' ) ÎA2 ? [GJ79]
    maksimaalse alamgraafikatte ülesanne
    Antud on orienteeritud graafid G = (V1 , A1) , 

    H = (V2 , A2) ja positiivne täisarv K . Kas leidub alamhulk R ÍV1´V2 , | R | ³K , mille puhul kõigi 
    <u, u'> , <v, v'> ÎR jaoks (u, v) ÎA1 siis ja ainult siis, kui ( u ', v ' ) ÎA2 ?
    maximum triangle packing 
    INSTANCE: Graph G = (V, E) .
    SOLUTION: A triangle packing for G , i.e., a collection V1 , V2 , … , Vk of disjoint subsets of V, each containing exactly 3 vertices, such that for each Vi = { ui , vi , wi } , 1 £ i £k , all three of the edges 

    < ui , vi > , < ui , wi > , and < vi , wi > belong to E . 
    MEASURE: Cardinality of the triangle packing, i.e., the number of disjoint subsets Vi . [CK00]
    maksimaalne kolmnurgapakk 
    VARIANT: graaf G = (V, E) .
    LAHEND: graafi G kolmnurgapakk, st hulga V ühisosata alamhulkade kogum V1 , V2 , … , Vk , nii et iga alamhulk Vi sisaldab täpselt kolm tippu, 

    Vi = { ui , vi , wi } , 1 £i£k , kusjuures kõik kolm serva < ui , vi > ,< ui , wi > ja < vi , wi > kuuluvad hulka E . 
    MÕÕT: kolmnurgapaki võimsus, st ühisosata alamhulkade Vi arv.
    McCulloch-Pitts neuron 
    A basic building block of neural networks. It receives one or more inputs and produces one or more identical outputs, each of which is a simple non-linear function of the sum of the inputs to the neuron. The non-linear function is typically a threshold or step function which is usually smoothed (i.e. a sigmoid) to facilitate learning. [CERN97]
    McCulloch-Pittsi neuron 
    Närvivõrkude põhiline ehituskivi. Omab ühe või mitu sisendit ja ühe või mitu identset väljundit, kusjuures iga väljund on lihtne mittelineaarne funktsioon sisendite summast. Mittelineaarne funktsioon on tavaliselt lävifunktsioon või treppfunktsioon, mida õppimise hõlbustamiseks tavaliselt silutakse (nn sigmoid).
    JOONIS
    McGee graph 
    The unique 7-cage graph consisting of the union of the two certain subgraphs. It has 24 nodes, 36 edges, and all nodes have degree 3. [EW00]
    McGee graaf 
    Ainus 7-puur, mis koosneb teatud kahe alamgraafi ühendist. 24 tippu, 36 serva, kõik servad astmega 3.
    JOONIS
    Menger's theorem 
    Minimax characterizations of connectivity by number of pairwise internally-disjoint or edge-disjoint paths between pairs of vertices. [DW96]
    Mengeri teoreem 
    Sidususe minimakskirjeldus tipupaaride vaheliste paariviisi ühisosata teede abil.
    meta-heuristic 
    This is a general framework for heuristics in solving hard problems. The idea of "meta" is that of level. An analogy is the use of a meta-language to explain a language. For computer languages, we use symbols, like brackets, in the meta-language to denote properties of the language being described, such as parameters that are optional. Examples of meta-heuristics are: 
    Besides parameters that define specific algorithms with each framework, these meta-heuristics also require some concept of representation, which is problem dependent. [HG99]
    metaheuristika 
    Heuristika üldstruktuur raskete ülesannete lahendamiseks. Termin "meta" tähendab taset. Analoogiliselt kasutatakse keele kirjeldamiseks metakeelt. Informaatikas kasutatakse metakeeltes teatud sümboleid (nt sulge) kirjeldatava keele omaduste (nt valikuliste parameetrite) tähistamiseks. Metaheuristikate näited: 
    • Sipelgoptimeerimine
    • Närvivõrgud 
    • Punktotsing
    • Simuleeritud lõõmutus 
    • Tabuotsing 
    • Sihtanalüüs 
    Lisaks parameetritele, mis määratlevad iga raammudeli jaoks kindlad algoritmid, nõuavad nimetatud metaheuristikad ka konkreetsest ülesandest olenevat esituskontseptsiooni.
    method
    A particular way of doing something, sometimes also called an algorithm or procedure. [EW00] 
    meetod
    Kindel viis millegi tegemiseks, nimetatakse ka algoritmiks või protseduuriks.
    metric 
    A real-valued symmetric nonnegative binary function that is 0 only when the arguments are equal and satisfies the triangle inequality. [DW96]
    meetrika 
    Reaalarvuliste väärtustega sümmeetriline mittenegatiivne kahendfunktsioon, mis rahuldab kolmnurga võrratust ning võrdub nulliga ainult võrdsete argumentide korral.
    metric dimension problem
    Given a graph G = (V, E) and positive integer 

    K £ | V | , is there a metric basis for G of cardinality K or less? [GJ79]
    meetrilise dimensiooni ülesanne
    Antud on graaf G = (V, E) ja positiivne täisarv 

    K £ | V | . Kas graafi G jaoks leidub meetriline baas võimsusega K või vähem?
    metric representation 
    An isometric embedding into a Cartesian product. [DW96]
    meetriline esitus 
    Isomeetriline kujutus otsekorrutisse.
    Meyniel graph 
    Graph in which every odd cycle of length at least 5 has at least two chords. [DW96]
    Meynieli graaf 
    Graaf, kus igal paaritul tsüklil pikkusega vähemalt 5 on vähemalt kaks kõõlu.
    JOONIS
    M-graph
    A graph in which there exist exactly two vertices of odd degree. [WM72]
    M-graaf
    Graaf, kus leidub täpselt kaks paaritu astmega tippu.
    JOONIS
    | # | 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