chapter 1.3 graph theory

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/19

encourage image

There's no tags or description

Looks like no tags are added yet.

20 Terms

1
New cards

tree

connected graph that contains no cycles

  • graphs with no cycles → acyclic


2
New cards

leaf

vertex of degree 1 in a tree

3
New cards

forest

a collection of one or more trees

4
New cards

binary decision tree

structure to facilitate searches and sorts and to model the logic of algorithms

5
New cards

bipartite graph

type of graph where vertices can be split into two separate, non overlapping groups, such that every edge connects a vertex in one group to a vertex in the other group

6
New cards

theorem: if a tree is of order n then T has ____ edges

n-1

7
New cards

Theorem: if f is a forest of order n containing k connected components, then F contains __ edges

n - k

8
New cards

a graph of order n is a tree iff __

it is connected and contains n-1 edges

or

it is acyclic and contains n-1 edges

9
New cards

connected

you can get from any vertex to any other vertex by following edges

10
New cards

let T be the tree of order n>=2

then T has at least two leaves

11
New cards

In any tree, the center is

either a single vertex or a pair of adjacent vertices

12
New cards

let T be a tree wit K edges. If G is a fraph whose minimum degree satisfies delta (G) >= k,

then G contains T as a subgraph. alternatively g contains every tree of order at most delta(G) + 1 as a subgraph

13
New cards

handshaking lemma

the sum of all vertex degrees = 2|E|

14
New cards

bridge

an edge that if you remove makes the graph become disconnected

15
New cards

cut vertex

a vertex that disconnects the graph when you remove it

16
New cards

spanning tree

of connected graph G is a subgraph that includes every vertex and is a tree so is connected and has no cycles

17
New cards

weight function

a function W that maps the edges of G to the nonnegative real numbers

18
New cards

weighted graph

the graph G together with a weighted function

19
New cards

minimum weight spanning tree

Given a connected, weighted graph G, the sum of the weights of the edges of T is no more than the sum for any other spanning tree of G

20
New cards

kruskal’s algorithm

Given : A connected , weighted graph G.

i . Find an edge of minimum weight and mark it .

ii . Among all of the unmarked edges that do not form a cycle with any of the marked edges , choose an edge of minimum weight and mark it .

iii . If the set of marked edges forms a spanning tree of G , then stop . If not , repeat step ii .