Graphs And Networks Flashcards
(24 cards)
What is a subgraph?
A subgraph is part of a graph.
What is a graph?
A graph consists on nodes which are connected by arcs.
When is a graph weighted?
When it has a number associated with each edge.
What is the degree or valency or order of a vertex?
The number of edges incident to it.
What is a path?
A path is a finite sequence of edges,such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
What is a walk?
A walk is a path in which you are permitted to return to verticies more than once.
What is a cycle?
A closed path.
When are verticies connected?
If there is a path between them. A graph is connected if all it’s verticies are connected.
What is a loop?
A loop is an edge that starts and finishes as the same vertex.
What is a simple graph?
A graph which there are no loops and not more than one edge connecting any pair of verticies.
What are digraphs?
Is the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.
What is a tree?
A connected graph with no cycles.
What is a spanning tree?
A spanning tree of a graph which includes all the verticies of the graph and is also a tree.
What is a bipartite graph?
It consists of two sets of verticies. Arcs only connect nodes between nodes in opposite sets.
What is a complete graph?
Is a graph in which every vertex is directly connected by an edge to each of the other verticies. If the graph has n verticies it is denoted by Kn.
What is an isomorphic graph?
It shows the same information but is drawn differently.
What is an adjacency matrix?
It records the number of direct links between the verticies.
What is a distance matrix?
It records the weights on the edges. Where there is no weight this is indicated by ‘-‘.
Give an advantage of first-fit bin packing.
It is quick
Give a disadvantage of first-fit bin packing.
Not likely to lead to a good solution.
Give an advantage of first-fit decreasing bin packing.
Easy to do
Usually a good solution
Give an disadvantage of first-fit decreasing bin packing.
Not necessarily an optimum solution.
Give an advantage of full bin packing.
Good solution
Give an disadvantage of full bin packing.
Difficult to do with lots of numbers/awkward numbers
