4.1 Graphs and Terminology

  1. What are the two foundations of a graph?
    They consist of vertices and edges.
  2. What does the notation G=(V,E) mean?
    • G = the graph
    • V = the set of vertices(nodes)
    • E = the set of edges.
  3. How many endpoints can a single edge have?
    An edge can be connected to either one or two vertices(nodes)
  4. What is a simple graph? 3 things.
    • A graph where
    • 1. Each edge connects to two different nodes
    • 2. Two nodes only has one direct way to connect with each-other, not two or more.
    • 3.
    • Image Upload 1
  5. What is a multi-graph?
    • Image Upload 2
    • Image Upload 3
  6. What is the multiplicity of a pair of nodes?
    If is equal to how many edges that connects the two nodes in the pair.
  7. What is a directed graph?
    explain each part of the notiation
    • G= the graph
    • V= the set vertecies/nodes
    • E= is the ordered set, collection, of edges between the nodes.
  8. When are two vertices adjacent?
    Two nodes are adjecent when they are connected by and edge,called incident. (just normal edge)
  9. What is the set called neighborhood of a node?
    N(v) is = the set of all nodes that are adjacent to the node v
  10. What is the degree of vertex? node
    • In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.
    • Image Upload 4
  11. What is an isolated vertex? How many degrees does it have?
    It has no connections, no adjacent nodes and therefor degree 0
  12. When is a vertex pendant?
    • A vertex is pendant if and only if it has
    • degree one.
    • Consequently, a pendant vertex is adjacent to exactly one other vertex.
  13. What is the handshaking theorem?
    Use on G=(V,E) and let G be an un-directed graph with m edges
    • Image Upload 5
    • Image Upload 6
  14. Finnish the sentance " an un-directed graph has an X number of vertices of y degree"
    " an undirected graph has an even number of vertecies of odd degree"
  15. What is meant by terminal vertex?
    • The vertex a is the initial vertex of
    • the edge and b the terminal vertex.
    • so terminal vertex just means the end point(node) of an edge
  16. What is in-degree of a vertex?
    it means how many edges has this node as its endpoint?<loops also count
  17. what is the out-degree of a node? vertex
    It means how many edges goes out from this node, loops also count
  18. What is a subgraph?
    Image Upload 7
  19. How do we know if two graphs are isomorphic?
    • When we can map each node in the same way in both graphs.
    • Image Upload 8
  20. How would an node/vertex list and a edgelist look using this graph?
    Image Upload 9
    Image Upload 10
  21. What is an adjacency matrix?
    preform on following graph
    Image Upload 11
    Image Upload 12
  22. When can we always know that the graph and the matrix will be symmetric?
    • When the graph is undirected.
    • either simple or multi etc
  23. What is the difference between an incidence matrix and a adjacency Matrix?
    • The adjacency matrix har nodes as both rows and columns
    • The incidence matrix has nodes as rows edges as columns
  24. When is a path a circuit?
    When it lead from one node through other and end on the same start node.
  25. When is a path called a simple path?
    when it does not contain a node more then once.
  26. when is a graph connected?
    Image Upload 13
  27. What is a cut vetrex and a cut edge?
    If the graph turns into two different disconnected systems then they are classified as cut ***
  28. What is a non-separable graph?
    a graph without cut vertices
  29. What is vertex connectivity?
    • In graph theory, a connected graph G is said to be
    • k-vertex-connected if it has more than k vertices and remains connected
    • whenever fewer than k vertices are removed.
  30. When is a graph strongly connected?
    Image Upload 14
  31. What is an Euler circuit?
    If is a cricut, path, that starts at a node and goes through all the nodes in the graph and ends up in the final graph.
  32. What is en Euler path?
    It is a path through all nodes in the graph but you don't have to end up at the start of the path in the end.
  33. When can we for sure say a graph an Euler path? 3 things
    G is a connected multigraph with at least two vertices if and ONLY IF each of the vertices nodes has en even degree. so 2 cennections.
  34. When can we for sure say a graph an Euler path and NOT a circut? 3 things
    • A connected multi graph has an Euler path but not an Euler circuit if and only if it has exactly two
    • vertices of odd degree.
  35. What is a hamilton path?
    a path in a simple graph that passes through every node in the graph
  36. What is a hamilton circut?
    a circut in a simple graph that passes through every node in the graph
  37. What is DiracĀ“s theorem?
    • Image Upload 15
    • Image Upload 16
  38. What is Ore's Theorem?
    • Image Upload 17
    • Image Upload 18
Card Set
4.1 Graphs and Terminology
snart klar:DD: