×
Get Full Access to Stony Brook U - AMS 301 - Class Notes - Week 3
Get Full Access to Stony Brook U - AMS 301 - Class Notes - Week 3

×

STONY BROOK U / Intro to Applied Statistics / STA 301 / What is a connected graph without circuits?

# What is a connected graph without circuits? Description

##### Description: These notes cover the lectures for the week of 2/29.
3 Pages 174 Views 0 Unlocks
Reviews

.lst-kix_7sl378fhtstc-1 > li:before{content:"- "}ul.lst-kix_bvalbyiyltal-6{list-style-type:none}ul.lst-kix_bvalbyiyltal-7{list-style-type:none}ul.lst-kix_bvalbyiyltal-4{list-style-type:none}ul.lst-kix_bvalbyiyltal-5{list-style-type:none}ul.lst-kix_bvalbyiyltal-2{list-style-type:none}ul.lst-kix_bvalbyiyltal-3{list-style-type:none}.lst-kix_7sl378fhtstc-0 > li:before{content:"- "}ul.lst-kix_bvalbyiyltal-0{list-style-type:none}ul.lst-kix_bvalbyiyltal-1{list-style-type:none}.lst-kix_7sl378fhtstc-5 > li:before{content:"- "}.lst-kix_83v58aijjsiw-6 > li:before{content:"- "}.lst-kix_7sl378fhtstc-3 > li:before{content:"- "}.lst-kix_7sl378fhtstc-7 > li:before{content:"- "}.lst-kix_83v58aijjsiw-8 > li:before{content:"- "}.lst-kix_7sl378fhtstc-2 > li:before{content:"- "}.lst-kix_7sl378fhtstc-6 > li:before{content:"- "}.lst-kix_83v58aijjsiw-7 > li:before{content:"- "}.lst-kix_7sl378fhtstc-4 > li:before{content:"- "}.lst-kix_83v58aijjsiw-0 > li:before{content:"- "}.lst-kix_bvalbyiyltal-6 > li:before{content:"- "}.lst-kix_bvalbyiyltal-5 > li:before{content:"- "}.lst-kix_bvalbyiyltal-3 > li:before{content:"- "}.lst-kix_83v58aijjsiw-5 > li:before{content:"- "}.lst-kix_bvalbyiyltal-4 > li:before{content:"- "}.lst-kix_83v58aijjsiw-4 > li:before{content:"- "}.lst-kix_83v58aijjsiw-3 > li:before{content:"- "}ul.lst-kix_bvalbyiyltal-8{list-style-type:none}.lst-kix_83v58aijjsiw-2 > li:before{content:"- "}.lst-kix_bvalbyiyltal-7 > li:before{content:"- "}.lst-kix_83v58aijjsiw-1 > li:before{content:"- "}.lst-kix_bvalbyiyltal-8 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-6{list-style-type:none}.lst-kix_bvalbyiyltal-1 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-7{list-style-type:none}ul.lst-kix_83v58aijjsiw-8{list-style-type:none}ul.lst-kix_7sl378fhtstc-0{list-style-type:none}ul.lst-kix_7sl378fhtstc-1{list-style-type:none}ul.lst-kix_7sl378fhtstc-2{list-style-type:none}ul.lst-kix_7sl378fhtstc-3{list-style-type:none}.lst-kix_bvalbyiyltal-2 > li:before{content:"- "}ul.lst-kix_7sl378fhtstc-4{list-style-type:none}ul.lst-kix_7sl378fhtstc-5{list-style-type:none}ul.lst-kix_7sl378fhtstc-6{list-style-type:none}ul.lst-kix_7sl378fhtstc-7{list-style-type:none}ul.lst-kix_7sl378fhtstc-8{list-style-type:none}.lst-kix_bvalbyiyltal-0 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-0{list-style-type:none}ul.lst-kix_83v58aijjsiw-1{list-style-type:none}ul.lst-kix_83v58aijjsiw-2{list-style-type:none}ul.lst-kix_83v58aijjsiw-3{list-style-type:none}.lst-kix_7sl378fhtstc-8 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-4{list-style-type:none}ul.lst-kix_83v58aijjsiw-5{list-style-type:none}

Section 3.1If you want to learn more check out What are the three primary agents of metamorphism?

If you want to learn more check out What is a process used to treat phobias?
We also discuss several other topics like What is pseudorandom?

Tree - a connected graph without circuitsIf you want to learn more check out Discuss what chargaff's rule is about.

We also discuss several other topics like What idea refers to a communal group of actors who believed in communism and revealing what the bottom of the social scale was like?

Theorem 1: if T is connected, these are equivalent (imply each other)

• T has no circuits
• If a is a node rh for every node x there exists a unique path between a and y.
• For every noe pair x and y, there exists a unique path between x and y
• T is minimally connected. Removing an edge and means T is no longer connected

We also discuss several other topics like mdu4003 uf

Theorem 2: A tree on n nodes has n-1 edges

Leaf - a node in a rooted tree, without children

Internal path - node in a rooted tree that isn’t a leaf

m-ary tree - each internal node has m children in this tree

Theorem 3 - An m-ary tree with i internal nodes has n≈mi+1 nodes

Corollary in an m-ary tree T

• i internal nodes imply leaves
•  leaves imply internal nodes and nodes
• H nodes imply  internal nodes and  leaves

Height - length of longest path between root and leaf

Balanced tree - a rooted tree is a balanced ifall

leaves are at level h or h-1 (within level in closeness)

Balanced                 Not balanced

Theorem 4: Let T be an m-ary tree of height h with l leaves;

•  and if tree is balanced

↖          Symbols means you round up                        ↗

A tree with nodes  must have at least 2 nodes of degree 1

list - seen but unexplored nodes

S - starting node

Put s on lit

Mark s as seen

While list contains node(s)

Pick a node i from list

If edge (i,j) exists with unseed node j

then mark j as seen

mark (i,j) as tree edge

put j on list

Otherwise remove j from list

This only finds all nodes if graph is connected

“Tree edges” don't form circuits

Page Expired
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here
References: