Thursday, November 13, 2014

My Eulergy


A student in my Graduate studies Discrete Mathematics class made great comment last week that it is very satisfying when there is opportunity to apply what we learn in our everyday lives. To that end, I will share a personal obsessive compulsive issue I have that I am now free of thanks to this weeks coursework.

I really enjoy doing long trail runs on Sundays. There is a state park very near me where you can run about a half marathon's distance seldom seeing the same tree twice. The issue is, as hard as I try, sooner or later I end up looping up on a path I have already done. My obsessive goal is to run the entire park, running each trail only once. As of yet, this is a goal unfulfilled!


I studied Euler, and Hamilton graphs and circuits among other things this week. Where as Leohnard Euler was concerned with traversing the edges of a connected multigraph, William Hamilton was concerned with traversing the vertices.

The trail running issue is more of an edges objective. Fortunately if you are concerned with edge paths, there are some handy formulas to help you classify paths (Hamilton, not so much). We learned that a Euler circuit is classified as path which travels all edges and returns to the point of origin. Also there is a Euler path, this is a path which travels all edges but in so doing does not return to the point of origin. I've also seen authors call these paths "Eulerian Walks" and "nearly-Eulerian"[2] Walks, as well as "open" and "closed" Euler paths.

Euler proved a convenient theorem which states that all Euler circuits must contain vertices of even degrees. The degree of a vertex is simply the number of edges connected to the vertex. Euler's theorem makes sense upon reflection because in a circuit a line never dead-ends, it goes through points and keeps on going. So, every time we traverse through a point we use two edges. One going in, and one going out. These increments of two yield all the even degreed vertices.

Alas, I look at my Calvert Cliffs trail map (Links to an external site.)[3] and I see right away places where paths intersect in three or five ways. Oh no! Is there any hope for my OCD? I had to take pause in hopes that perhaps all is not lost. Then, I looked instead for a Euler path.

Euler says that we can have a Euler path, but only if our graph contains exactly two vertices of odd degrees. This also makes sense if you buy the Euler circuit explanation above. Simply imagine that you have two separate Euler Circuits and then you bridge them with one single line. Now observe, where you have added that edge. By joining the vertices in the previously separate graphs you have a incremented the degree of each by one. They were even, so now, they are both odd. So, in the resulting Euler path every line is traced in the first subgraph. We then trace across the bridge we added to the next subpath. Finally every line is traced in the second Euler circuit subgraph. We cannot cross the bridge again to get back to the origin, however, as a small concession at-least every edge has been traversed. Viola! Euler path.

Now I turn back to my running graph and look, there are actually more than two odd degreed edges, and unfortunately a pendant (the point by the water sticks out all in it's own with degree 1). I can however tweak some of the points into being even numbers. I do this in two ways. First, I  can generalize clusters of three way intersection as single n-degree points. The yellow circles are examples of places where I unified the intersections. Second, I added a new path which I make by running out to street bordering the front of the park. Lastly to deal with the pendant I figure, I can either give up and remove the line, or just have my run end at the end of the pendant.

Armed with my new graph that has only two odd numbered vertices I toast to mister Euler and start tracing. Twenty minutes later I am consulting the text book. After 5 failed attempts I have not found a Euler path! Perhaps I misread the theorem?

Trying again I do something different I start at one of the odd degreed vertices. Success! After this I notice something, any path I try which does not start and end at an odd degreed vertex is doomed to fail. I go to the library and after further research I find this:

"If the degree of both u and v is odd, then G, has a walk which begins at point u, contains every line of Gi exactly once and ends at point v; let us call Gu in this case nearly-Eulerian with respect to u and v."[2] So yes, this confirms it. You have to start and stop on a point which connects an odd number of trails for it to work.

It turns out that this is even true for pendants. Like the one I initially removed in red on the graph above. After all if you connect the pendant to an odd degree vertex, you've just made the connecting point even, and the far end of the pendant is still degree one. One is odd right? So, now I realize that I will be making the walk to the beach on the path I previously removed after all. Why not?

I'm happy to have a cure for my issue. It is a bummer though that after such a long run, I am at the furthest point from the parking lot. Oh well. I won't spoil it for you. Trace the graph and see if you can find the Euler path. I will put my answer in white font inside the brackets below, yours could be different: 
{k,n,m,i,j,h,e,p,o,q,r,b,a,g,f,c,d,s,t,water}
References:
[1] Rosen, Kenneth. Discrete Mathematics and Its Applications. Seventh Edition. New York: McGraw-Hill, 2012. 
[2] S. Goodman, Hedentniem S., Eulerian Walks in Graphs, SIAM Journal of Computing, Vol.2, No 1, March 1973
[3] mrhyker@midatlantichikes.com, http://www.midatlantichikes.com/calvercliffs.htm, (Links to an external site.) MidAtlanticHeights.com, April 2010

Friday, July 4, 2014

Chocolate Oatmeal Milk Stout

Quinn's Chocolate Oatmeal Milk Stout - ENJOY!
Boiled in late April, double fermented in glass carboys, bottled late May

Steeping grains at 150-158 for 30 min.

wort..(148F for 60+ min):
1 lbs  Black Patent Malt  (Annapolis Homebrew SKU: 18011)
8 oz lbs Carapils (Annapolis Homebrew SKU: 17110)
12 oz Chocolate Malt ((Annapolis Homebrew SKU: 17010)
8 oz Crystal 80 (Annapolis Homebrew SKU: 17111)
½ lb oats

boil:
1.5 oz Goldings at 60 min (same SKU as hopes below)
6 lbs Light Bulk Extract .. added in last 20 min or so (Annapolis Homebrew SKU: 25605)
1 lbs Lactose added last 15 min of boil (Annapolis Homebrew SKU: 27006)
.5 oz Goldings at 15 min (Annapolis Homebrew SKU: 20145)

yeast SafAle S-04 (Annapolis Homebrew SKU: 21008)

bottled w/ 4oz karo syrup





Saturday, May 24, 2014

Hefeweizen


I'm making a wheat beer today. It's a partial mash kit I bought from Annapolis Home brew. There are four pounds or Weyermann grains in this brew: three pounds Pale Wheat, three-quarters of a pound Pilsen, and a quarter pound Carafoam. There's also a little over four pounds of liquid malt extract in this partial. I'm not sure the type, it's light,  but not completely blonde. I'll be throwing about 2 ounces of Perle hops in at the beginning of the boil and a half an ounce of Hallertau in about fifteen minutes from the end of the boil.

I'm mashing now. This is the process where the sugars are leached from the grain in a hot water bath. The mash started at about 148 degrees F, which seems to be a temperature suited to both the wheat and barleys in the grain blend. To keep things steady I put the lid on my five gallon boil pot, wrap towels and blankets around it and put it in a big insulated cooler. This will give me an hour to do something I should have done quite a while ago. Blog my brewing.

Since we our return to the mainland, the change in seasons has inspired me to brew again. The crisp onset of Fall, changes in colors, and hearth of seasonal baked treats to warm chapped cheeks is a shoe-in for the malty smell of home brewing, and the mouthfeel and swallow of a home loved porter. I started again in September of 2013. Years ago I brewed in Norfolk Virginia with an interesting friend Mike Calderone. We occasionally made a good batch together, but more than that it was just something fun to do while watching a football game and getting families together. That was 2006, so the hiatus went about seven years.

I've been surprised how good the beers have come out in this my Act 2. Even Sue enjoys them. I think really it's about water, and cleaning. We've got better water here, and with age I've become more conscious of how to keep equipment better sanitized.  It's a shame that  I haven't kept track of the ten or so batches I've brewed in the last 6 months but I can probably at least recall what they've been. Here goes:
  • Stella Artois Clone
  • Honey Brown Ale
  • Pumpkin Ale
  • Nutella Porter
  • Brewferm Belgian Triples
  • Oatmeal Stout
  • Caribou Slobber Brown Ale (Northern Brewer)
  • Tequilla Oak Casked Golden Ale
  • Brewferm Diablo (Golden Ale)
  • Cocoa Oatmeal Milk Stout
  • Today's Hefeweizen
Cheers!

PS: starting gravity 1.040