Graph Theory

EUinterpreter
114 words 7 learners

Learn words with Flashcards and other activities

Definition First
Print Flashcards

Other learning activities

Answer a few questions about each word. Use this to prep for your next quiz! Compete with other teams in real time to see who answers the most questions correctly! Test your spelling acumen. Read the definition, listen to the word and try spelling it!

Teaching tools

Create and assign quizzes to your students to test their vocabulary. Assign learning activities including Practice, Vocabulary Jams and Spelling Bees to your students, and monitor their progress in real-time.

Full list of words from this list:

words only definitions & notes
  1. antiparallel
    (especially of vectors) parallel but oppositely directed
    C 1 is a

    loop , C 2 is a

    digon (a pair of parallel undirected edges in a multigraph , or a pair of antiparallel edges in a directed graph), and C 3 is called a

    triangle .
  2. convex polyhedron
    a polyhedron any plane section of which is a convex polygon
    In the familiar case of a 3-connected simple planar graph G (isomorphic to a convex polyhedron P ), the dual G * is also a 3-connected simple planar graph (and isomorphic to the dual polyhedron P * ).
  3. nonadjacent
    not adjacent; not next
    A

    strongly regular graph is a regular graph such that any adjacent vertices have the same number of common neighbors as other adjacent pairs and that any nonadjacent vertices have the same number of common neighbors as other nonadjacent pairs.
  4. acyclic
    not cyclic
    A graph is

    acyclic if it contains no cycles;

    unicyclic if it contains exactly one cycle; and

    pancyclic if it contains cycles of every possible length (from 3 to the order of the graph).
  5. isomorphic
    having similar appearance but genetically different
    Two graphs G and H are said to be

    isomorphic , denoted by G ~ H , if there is a one-to-one correspondence, called an

    isomorphism , between the vertices of the graph such that two vertices are adjacent in G if and only if their corresponding vertices are adjacent in H .
  6. vertex
    the highest point of something
    A

    graph G consists of two types of elements, namely vertices and edges .
  7. graph
    a visual representation of the relations between quantities
    Graph theory is a growing area in mathematical research, and has a large specialized vocabulary.
  8. planar
    involving two dimensions
    A

    planar graph is one which can be drawn on the (Euclidean) plane without any crossing; and a

    plane graph , one which is drawn in such fashion.
  9. homomorphism
    similarity of form
    Likewise, a graph G is said to be

    homomorphic to a graph H if there is a mapping, called a

    homomorphism , from V ( G ) to V ( H ) such that if two vertices are adjacent in G then their corresponding vertices are adjacent in H .
  10. factorization
    breaking down an integer or polynomial into its divisors
    A partition of edges of a graph into k -factors is called a

    k -factorization .
  11. adjacency
    the attribute of being so near as to be touching
    A

    subgraph of a graph G is a graph whose vertex set is a subset of that of G , and whose adjacency relation is a subset of that of G restricted to this subset.
  12. disjoint
    having no elements in common
    Two paths are

    internally disjoint (some people call it independent ) if they do not have any vertex in common, except the first and last ones.
  13. polynomial
    a mathematical function that is the sum of a number of terms
    An undirected graph's

    Wiener polynomial is defined to be Σ q d ( u , v ) over all unordered pairs of vertices u and v .
  14. undirected
    aimlessly drifting
    C 1 is a

    loop , C 2 is a

    digon (a pair of parallel undirected edges in a multigraph , or a pair of antiparallel edges in a directed graph), and C 3 is called a

    triangle .
  15. rational number
    an integer or the quotient of two integers
    They may be restricted to rational numbers or integers.
  16. bipartite
    involving two sections or elements
    One theorem is that a graph is bipartite if and only if it contains no odd cycles.
  17. isomorphism
    similarity or identity of form or shape or structure
    The difference between a labeled and an unlabeled graph is that the latter has no specific set of vertices or edges; it is regarded as another way to look upon an isomorphism type of graphs.
  18. endpoint
    a place where something ends or is complete
    Every edge has two endpoints in the set of vertices, and is said to

    connect or

    join the two endpoints.
  19. multipartite
    involving more than two parties
    A graph that can be decomposed into two partite sets

    bipartite ; three sets ,

    tripartite ; k sets ,

    k -partite ; and an unknown number of sets,

    multipartite .
  20. reachable
    easily approached
    Informally, a strongly connected component of a directed graph is a subgraph where all nodes in the subgraph are reachable by all other nodes in the subgraph.
  21. maximal
    the greatest or most complete or best possible
    The notion of maximality is defined dually : G is

    maximal with P provided that P ( G ) and G has no proper supergraph H such that P ( H ).
  22. subset
    a group whose members are members of another group
    A

    subgraph of a graph G is a graph whose vertex set is a subset of that of G , and whose adjacency relation is a subset of that of G restricted to this subset.
  23. polyhedron
    a solid figure bounded by plane polygons or faces
    In the familiar case of a 3-connected simple planar graph G (isomorphic to a convex polyhedron P ), the dual G * is also a 3-connected simple planar graph (and isomorphic to the dual polyhedron P * ).
  24. subscript
    character printed slightly below and to the side of another
    The subscript G is usually dropped when there is no danger of confusion; the same neighborhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs.
  25. maximally
    to a maximal degree
    A

    component is a maximally connected subgraph.
  26. digraph
    two successive letters
    A

    loop in a digraph, however, keeps a sense of direction and treats both head and tail identically.
  27. natural number
    the number 1 and any other number obtained by adding 1 to it repeatedly
    (

    Graph labeling usually refers to the assignment of labels (usually natural numbers , usually distinct) to the edges and vertices of a graph, subject to certain rules depending on the situation.
  28. unlabeled
    lacking a label or tag
    Graphs whose edges or vertices have names or labels are known as

    labeled , those without as

    unlabeled .
  29. disconnect
    separate, sever, or unfasten
    (That is, a tree with the connectivity requirement removed; a graph containing multiple disconnected trees.)
  30. regular hexagon
    a hexagon with six sides of equal length
    A

    theta 0 graph has seven vertices which can be arranged as the vertices of a regular hexagon plus an additional vertex in the center.
  31. concatenate
    add by linking or joining so as to form a chain or series
    [ 2 ]

    Connectivity extends the concept of adjacency and is essentially a form (and measure) of concatenated adjacency .
  32. Wiener
    United States mathematician and founder of cybernetics
    The

    Wiener index of a vertex v in a graph G , denoted by W G ( v ) is the sum of distances between v and all others.
  33. edgeless
    lacking a cutting edge
    An

    edgeless graph or

    empty graph or

    null graph is a graph with zero or more vertices, but no edges.
  34. diam
    the length of a straight line passing through the center of a circle and connecting two points on the circumference
    The

    diameter diam( G ) of a graph G is the maximum eccentricity over all vertices in a graph; and the

    radius rad( G ), the minimum.
  35. connectivity
    the property of being connected or the degree to which something has connections
    (That is, a tree with the connectivity requirement removed; a graph containing multiple disconnected trees.)
  36. edge in
    push one's way into (a space)
    More formally, for two vertices and , is a non-edge in a graph whenever is not an edge in .
  37. Boolean
    of or relating to a combinatorial system devised by George Boole that combines propositions with the logical operators AND and OR and IF THEN and EXCEPT and NOT
    Alternative models of graphs exist; e.g., a graph may be thought of as a Boolean binary function over the set of vertices or as a square (0,1)- matrix .
  38. interchangeably
    in an interchangeable manner
    These two sets of definitions are often used interchangeably.)
  39. trivalent
    having a valence of three
    A 3-regular graph is said to be

    cubic , or trivalent .
  40. invariant
    unvarying in nature
    A

    graph invariant is a property of a graph G , usually a number or a polynomial, that depends only on the isomorphism class of G .
  41. clique
    an exclusive circle of people with a common purpose
    A

    clique in a graph is a set of pairwise adjacent vertices.
  42. oriented
    adjusted or located in relation to surroundings
    A

    digraph , or directed graph , or

    oriented graph , is analogous to an undirected graph except that it contains only arcs.
  43. orient
    the eastern hemisphere
    A

    digraph , or directed graph , or

    oriented graph , is analogous to an undirected graph except that it contains only arcs.
  44. connect
    fasten or put together two or more pieces
    Every edge has two endpoints in the set of vertices, and is said to

    connect or

    join the two endpoints.
  45. spanner
    a hand tool that is used to hold or twist a nut or bolt
    A

    k -spanner is a spanning subgraph, S, in which every two vertices are at most k times as far apart on S than on G. The number k is the

    dilation . k -spanner is used for studying geometric network optimization.
  46. second power
    the product of two equal terms
    A second power of a graph is also called a

    square .
  47. edge
    a line determining the limits of an area
    A

    graph G consists of two types of elements, namely vertices and edges .
  48. node
    any thickened enlargement
    A

    vertex is simply drawn as a node or a dot .
  49. unordered
    not arranged in order
    An undirected graph's

    Wiener polynomial is defined to be Σ q d ( u , v ) over all unordered pairs of vertices u and v .
  50. embed
    fix or set securely or deeply
    A graph that does not contain H as an induced subgraph is said to be

    H -free . [ citation needed ]

    A

    universal graph in a class

    K of graphs is a simple graph in which every element in

    K can be embedded as a subgraph.
  51. trivially
    in a frivolously trivial manner
    Trivially, diam( G ) ≤ 2 rad( G ).
  52. valency
    the phenomenon of forming chemical bonds
    The

    degree , or valency , d G ( v ) of a vertex v in a graph G is the number of edges incident to v , with loops being counted twice.
  53. traversable
    capable of being traversed
    A graph that contains an Eulerian trail is

    traversable .
  54. integer
    any natural number or its negative, or zero
    A sequence of non-increasing integers is

    realizable if it is a degree sequence of some graph.
  55. algorithm
    a precise rule specifying how to solve some problem
    A directed graph can be decomposed into strongly connected components by running the depth-first search (DFS) algorithm twice: first, on the graph itself and next on the transpose graph in decreasing order of the finishing times of the first DFS.
  56. outgo
    be or do something to a greater degree
    A

    knot in a directed graph is a collection of vertices and edges with the property that every vertex in the knot has outgoing edges, and all outgoing edges from vertices in the knot terminate at other vertices in the knot.
  57. real number
    any rational or irrational number
    Weights are usually real numbers .
  58. decompose
    break down
    A directed graph can be decomposed into strongly connected components by running the depth-first search (DFS) algorithm twice: first, on the graph itself and next on the transpose graph in decreasing order of the finishing times of the first DFS.
  59. denote
    have as a meaning
    The

    vertex set of G is usually denoted by V ( G ), or V when there is no danger of confusion.
  60. hexagon
    a six-sided polygon
    A

    theta 0 graph has seven vertices which can be arranged as the vertices of a regular hexagon plus an additional vertex in the center.
  61. cycle
    a periodically repeated sequence of events
    The closed equivalent to this type of walk, a walk that starts and ends at the same vertex but otherwise has no repeated vertices or edges, is called a

    cycle .
  62. realizable
    capable of being realized
    A sequence of non-increasing integers is

    realizable if it is a degree sequence of some graph.
  63. theta
    the 8th letter of the Greek alphabet
    A

    theta graph is the union of three internally disjoint (simple) paths that have the same two distinct end vertices.
  64. adjacent
    having a common boundary or edge
    The two endpoints of an edge are also said to be

    adjacent to each other.
  65. transpose
    change the order or arrangement of
    A directed graph can be decomposed into strongly connected components by running the depth-first search (DFS) algorithm twice: first, on the graph itself and next on the transpose graph in decreasing order of the finishing times of the first DFS.
  66. dag
    a flap along the edge of a garment
    The partial order structure of directed acyclic graphs (or DAGs) gives them their own terminology.
  67. component
    one of the individual parts making up a larger entity
    A related but weaker concept is that of a strongly connected component .
  68. arc
    a continuous portion of a circle
    This means that there is either no edge between the two vertices or (for directed graphs) at most one of and from is an arc in G.

    Occasionally the term

    cotriangle or

    anti-triangle is used for a set of three vertices none of which are connected.
  69. matrix
    an enclosure within which something originates or develops
    Alternative models of graphs exist; e.g., a graph may be thought of as a Boolean binary function over the set of vertices or as a square (0,1)- matrix .
  70. euclidean
    relating to geometry as developed by Euclid
    A

    planar graph is one which can be drawn on the (Euclidean) plane without any crossing; and a

    plane graph , one which is drawn in such fashion.
  71. optimization
    the act of rendering optimal
    A

    k -spanner is a spanning subgraph, S, in which every two vertices are at most k times as far apart on S than on G. The number k is the

    dilation . k -spanner is used for studying geometric network optimization.
  72. sense of direction
    an awareness of your orientation in space
    An

    undirected edge disregards any sense of direction and treats both endvertices interchangeably.
  73. chromatic
    being, having, or characterized by color
    The

    chromatic number χ (G) is the smallest k for which G has a k -colouring.
  74. dominate
    be in control
    A

    dominating set of a graph is a vertex subset whose closed neighborhood includes all vertices of the graph.
  75. one-to-one
    used of relations such that each member of one set is associated with one member of a second set
    Two graphs G and H are said to be

    isomorphic , denoted by G ~ H , if there is a one-to-one correspondence, called an

    isomorphism , between the vertices of the graph such that two vertices are adjacent in G if and only if their corresponding vertices are adjacent in H .
  76. label
    a brief description given for purposes of identification
    Graphs whose edges or vertices have names or labels are known as

    labeled , those without as

    unlabeled .
  77. unreachable
    inaccessibly located or situated
    When u and v are unreachable from each other, their distance is defined to be infinity ∞.
  78. qualification
    the act of modifying or changing the strength of some idea
    When stated without any qualification, a graph is usually assumed to be simple, except in the literature of

    category theory , where it refers to a

    quiver .
  79. rad
    a unit of absorbed ionizing radiation equal to 100 ergs per gram of irradiated material
    The

    diameter diam( G ) of a graph G is the maximum eccentricity over all vertices in a graph; and the

    radius rad( G ), the minimum.
  80. labeled
    bearing or marked with a label or tag
    Graphs whose edges or vertices have names or labels are known as

    labeled , those without as

    unlabeled .
  81. matching
    being two identical
    A 1-regular graph is a matching.
  82. orientation
    the act of determining one's position
    An

    orientation is an assignment of directions to the edges of an undirected or partially directed graph.
  83. dual
    consisting of two parts or components, usually in pairs
    The notion of maximality is defined dually : G is

    maximal with P provided that P ( G ) and G has no proper supergraph H such that P ( H ).
  84. loop
    anything with a round or oval shape
    [ 1 ]

    A

    loop is an edge whose endpoints are the same vertex.
  85. finite
    bounded in magnitude or spatial or temporal extent
    A graph is

    infinite if it has infinitely many vertices or edges or both; otherwise the graph is

    finite .
  86. isolate
    place or set apart
    A vertex of degree 0 is an

    isolated vertex .
  87. span
    the distance or interval between two points
    A subgraph H is a

    spanning subgraph , or

    factor , of a graph G if it has the same vertex set as G .
  88. dilation
    the act of making an opening wider
    A

    k -spanner is a spanning subgraph, S, in which every two vertices are at most k times as far apart on S than on G. The number k is the

    dilation . k -spanner is used for studying geometric network optimization.
  89. triangle
    a three-sided polygon
    This means that there is either no edge between the two vertices or (for directed graphs) at most one of and from is an arc in G.

    Occasionally the term

    cotriangle or

    anti-triangle is used for a set of three vertices none of which are connected.
  90. eccentricity
    strange and unconventional behavior
    The

    eccentricity ε G ( v ) of a vertex v in a graph G is the maximum distance from v to any other vertex.
  91. disconnected
    having been broken up or divided into parts or pieces
    (That is, a tree with the connectivity requirement removed; a graph containing multiple disconnected trees.)
  92. connected
    joined or linked together
    This means that there is either no edge between the two vertices or (for directed graphs) at most one of and from is an arc in G.

    Occasionally the term

    cotriangle or

    anti-triangle is used for a set of three vertices none of which are connected.
  93. kernel
    a single whole grain of a cereal
    A

    kernel in a (possibly directed) graph G is an independent set S such that every vertex in V(G) \ S dominates some vertex in S. In undirected graphs, kernels are maximal independent sets.
  94. outermost
    situated at the farthest possible point from a center
    Furthermore, since we can establish a sense of "inside" and "outside" on a plane, we can identify an "outermost" region that contains the entire graph if the graph does not cover the entire plane.
  95. correspond
    take the place of or be parallel or equivalent to
    Two graphs G and H are said to be

    isomorphic , denoted by G ~ H , if there is a one-to-one correspondence, called an

    isomorphism , between the vertices of the graph such that two vertices are adjacent in G if and only if their corresponding vertices are adjacent in H .
  96. directed
    (often used in combination) having a specified direction
    An edge can thus be defined as a set of two vertices (or an ordered pair, in the case of a

    directed graph - see Section Direction ).
  97. degree
    a specific identifiable position in a continuum or series
    An infinite graph where every vertex has finite degree is called

    locally finite .
  98. multiplicity
    the property of having more than one part or entity
    The

    multiplicity of an edge is the number of multiple edges sharing the same end vertices; the

    multiplicity of a graph , the maximum multiplicity of its edges.
  99. dominating
    offensively self-assured or exercising unwarranted power
    A

    dominating set of a graph is a vertex subset whose closed neighborhood includes all vertices of the graph.
  100. injection
    the forceful insertion of a substance under pressure
    A minor of is an injection from to such that every edge in corresponds to a path (disjoint from all other such paths) in such that every vertex in is in one or more paths, or is part of the injection from to .
  101. induce
    cause to act in a specified manner
    A subgraph H of a graph G is said to be

    induced (or

    full ) if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has exactly the edges that appear in G over the same vertex set.
  102. weighted
    made heavy or weighted down with weariness
    A

    weighted graph associates a label (

    weight ) with every edge in the graph.
  103. pendant
    an adornment that hangs from a piece of jewelry
    Nous n'existons que grâce à vos dons !

    Si chaque lecteur de cette bannière donne 10 €, nous pourrons subvenir aux besoins de Wikipédia pendant un an.
  104. tripartite
    involving three parties or elements
    A graph that can be decomposed into two partite sets

    bipartite ; three sets ,

    tripartite ; k sets ,

    k -partite ; and an unknown number of sets,

    multipartite .
  105. path
    an established line of travel or access
    Traditionally, a

    path referred to what is now usually known as an open walk .
  106. direct
    proceeding without interruption
    An edge can thus be defined as a set of two vertices (or an ordered pair, in the case of a

    directed graph - see Section Direction ).
  107. notation
    a comment or instruction (usually added)
    Since any subgraph induced by a clique is a complete subgraph, the two terms and their notations are usually used interchangeably.
  108. infinity
    time without end
    The girth and circumference of an acyclic graph are defined to be infinity ∞.
  109. binary
    of or pertaining to a number system having 2 as its base
    Alternative models of graphs exist; e.g., a graph may be thought of as a Boolean binary function over the set of vertices or as a square (0,1)- matrix .
  110. identifiable
    capable of being recognized
    (Thus, this usage distinguishes between graphs with identifiable vertex or edge sets on the one hand, and isomorphism types or classes of graphs on the other.)
  111. tree
    a tall perennial woody plant having a main trunk and branches forming a distinct elevated crown; includes both gymnosperms and angiosperms
    A

    tree is a connected acyclic simple graph.
  112. articulation
    the manner in which things come together and are connected
    A

    cut vertex , or articulation point , is a vertex whose removal disconnects the remaining subgraph.
  113. connotation
    an idea that is implied or suggested
    In graph theory, the word independent usually carries the connotation of pairwise disjoint or mutually nonadjacent .
  114. girth
    the distance around something, especially a person's body
    The

    girth of a graph is the length of a shortest (simple) cycle in the graph; and the

    circumference , the length of a longest (simple) cycle.
Created on Wed Nov 21 21:29:52 EST 2012

Sign up now (it’s free!)

Whether you’re a teacher or a learner, Vocabulary.com can put you or your class on the path to systematic vocabulary improvement.