-
What are the two foundations of a graph?
They consist of vertices and edges.
-
What does the notation G=(V,E) mean?
- G = the graph
- V = the set of vertices(nodes)
- E = the set of edges.
-
How many endpoints can a single edge have?
An edge can be connected to either one or two vertices(nodes)
-
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.
-
-
What is the multiplicity of a pair of nodes?
If is equal to how many edges that connects the two nodes in the pair.
-
What is a directed graph?
explain each part of the notiation
G=(V,E)
- G= the graph
- V= the set vertecies/nodes
- E= is the ordered set, collection, of edges between the nodes.
-
When are two vertices adjacent?
Two nodes are adjecent when they are connected by and edge,called incident. (just normal edge)
-
What is the set called neighborhood of a node?
N(v) is = the set of all nodes that are adjacent to the node v
-
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.
-
What is an isolated vertex? How many degrees does it have?
It has no connections, no adjacent nodes and therefor degree 0
-
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.
-
What is the handshaking theorem?
Use on G=(V,E) and let G be an un-directed graph with m edges
-
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"
-
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
-
What is in-degree of a vertex?
it means how many edges has this node as its endpoint?<loops also count
-
what is the out-degree of a node? vertex
It means how many edges goes out from this node, loops also count
-
-
How do we know if two graphs are isomorphic?
- When we can map each node in the same way in both graphs.
-
How would an node/vertex list and a edgelist look using this graph?
-
What is an adjacency matrix?
preform on following graph
-
When can we always know that the graph and the matrix will be symmetric?
- When the graph is undirected.
- either simple or multi etc
-
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
-
When is a path a circuit?
When it lead from one node through other and end on the same start node.
-
When is a path called a simple path?
when it does not contain a node more then once.
-
when is a graph connected?
-
What is a cut vetrex and a cut edge?
If the graph turns into two different disconnected systems then they are classified as cut ***
-
What is a non-separable graph?
a graph without cut vertices
-
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.
-
When is a graph strongly connected?
-
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.
-
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.
-
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.
-
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.
-
What is a hamilton path?
a path in a simple graph that passes through every node in the graph
-
What is a hamilton circut?
a circut in a simple graph that passes through every node in the graph
-
-
|
|