Study of cerebral vascular structure broadens our understanding of underlying variations, such as pathologies that can lead to cerebrovascular disorders. The development of high resolution 3D imaging modalities has provided us with the raw material to study the blood vessels in small animals such as mice. However, the high complexity and 3D nature of the cerebral vasculature make comparison and analysis of the vessels difficult, time-consuming and laborious. Here we present a framework for automated segmentation and recognition of the cerebral vessels in high resolution 3D images that addresses this need. The vasculature is segmented by following vessel center lines starting from automatically generated seeds and the vascular structure is represented as a graph. Each vessel segment is represented as an edge in the graph and has local features such as length, diameter, and direction, and relational features representing the connectivity of the vessel segments. Using these features, each edge in the graph is automatically labeled with its anatomical name using a stochastic relaxation algorithm. We have validated our method on micro-CT images of C57Bl/6J mice. A leave-one-out test performed on the labeled data set demonstrated the recognition rate for all vessels including major named vessels and their minor branches to be > 75%. This automatic segmentation and recognition methods facilitate the comparison of blood vessels in large populations of subjects and allow us to study cerebrovascular variations.